搜索和递归：二分搜索及二分搜索的递归实现

线性搜索按顺序遍历序列时间复杂度O(n)。二分搜索在有序从大到小 / 从小到大的序列中可以以更低时间复杂度完成搜索。非递归的二分搜索在有序的设为从小到大排序数组中先设下标标记第一个元素为first最后一个元素为last。计算中间元素middle (first last) / 2要查找的目标元素与middle所指元素比较大小较小则把last设为 middle - 1 较大则把first设为 middle 1 循环这一过程重点循环条件从边界条件看当二分搜索即将结束时假设arr.size() 10first与last相邻假设分别为first 3last 4。此时的middle 3。假设目标元素target。如果target middle令last middle - 1 2目标元素不存在。如果target middle令first middle 1 4则下一次查找middle 4。继续最后一步查找。如果target middle查找结束找到目标元素。所以可以将循环设为while (first last)#include iostream int BinarySearch(int arr[], int size, int val) { int first 0, last size - 1, middle (first last) / 2; while (first last) { if (val arr[middle]) { last middle - 1; } else if (val arr[middle]) { first middle 1; } else return middle; middle (first last) / 2; } return -1; } int main() { int arr[] { 12, 21, 36, 52, 64, 79, 81, 90, 94, 100 }; int index BinarySearch(arr, 10, 64); if (index -1) std::cout Element not found! std::endl; else std::cout Index of the element is: index std::endl; }这里的参数int arr[] 是代表数组的指针传递的是数组的首地址。这种传递方式不会传递整个数组并且在函数中对数组进行修改会改变原数组。在传递过程中会丢失数组的大小信息可以一起传递给函数。可以用const修饰这个参数防止修改原数组const int arr[]时间复杂度分析线性搜索O(n)二分搜索O(logn)对数时间复杂度log以2为底的n就以代码中的数组进行建模按照二分搜索的逻辑顺序进行分析我们可以得到一个BST树Binary search tree二分搜索树一个二叉树我们按照while循环的次数层层递进可以得到这样的逻辑结构左子树代表val middle后下一次循环的middle值右子树代表val middle后的middle值64/ \21 90/ \ / \12 36 79 94\ \ \52 81 100对于树中的每一个节点其具有以下性质1. 左子树的每一个节点的值 小于 当前节点的值2. 右子树的每一个节点的值 大于 当前节点的值3. 左右子树分别也是BST二分搜索算法实际上就是沿着这颗BST从root开始搜索的过程每一次搜索只会沿着一条路径搜索下去。二分搜索算法的时间复杂度与搜索次数相关联搜索次数最多就是上面这棵BST的层数。把BST树看作一般的二叉树假设每层的节点是满的每个节点都有左右两个子节点。首先我们推导层数和数据规模的关系每层节点的个数第一层第二层第三层第四层…第层节点的个数假设每层的节点都是满的。二叉树的数据规模等比数列求和公式或错位相减法时间复杂度与层数相关从上面的推导可以直接得到与的关系所以得到二分搜索的时间复杂度为二分搜索递归方法递归核心思想递归的形式函数自己调用自己。递归的目的在数据规模为n且n很大的情况下——不断划分数据规模直到数据规模很小小到问题的结果是已知的。递缩小数据规模递归的实现从调用的函数得到已知的答案然后用这个答案进行这一步的操作再将得出的答案传递给上一层函数并最终得出结果。归汇总最终答案递归算法的特点1. 同一个算法下不管哪一层数据规模的递归求解问题的方式是一样的。2. 不同规模的数据上一层递归和下一层递归之间其计算结果是有关系可循的。3. 递归函数有尽头递归不适合处理大量数据否则容易栈溢出。4. 递归的限制每次调用函数都要开辟新的栈帧大量数据情况下使用递归栈空间容易溢出。递归设计的原则函数体本身简单要搞清楚递归的意义是什么返回值和参数列表的含义它们能完成什么功能。一定有递归结束的条件。写好每层数据规模之间的计算关系。二分搜索的递归数组上递归的规模缩减实际是范围的缩减需要起始点和结束点的下标通过下标的修改影响范围。函数的意义在arr数组的first到last范围内二分搜索val找到则返回val的下标找不到返回 -1需要的参数arr val first last进行的操作计算middle结束的条件val arr[middle]找到元素first last没有元素需要返回的值找到元素返回索引找不到返回-1二分在val middle三种情况下不同的分支代码实现#include iostream int ReBinSearch(int arr[], int val, int first, int last) { if (last first) //未找到时递归的结束条件 return -1; int middle (first last) / 2; //二分搜索 if (val arr[middle]) return ReBinSearch(arr, val, first, middle - 1); if (val arr[middle]) return ReBinSearch(arr, val, middle 1, last); if (val arr[middle]) //找到时递归的结束条件 return middle; } int main() { int arr[] { 12, 21, 36, 52, 64, 79, 81, 90, 94, 100 }; int index ReBinSearch(arr, 81, 0, 9); //在第二个参数输入要找的目标值 if (index -1) std::cout Element not found! std::endl; else std::cout Index of the element is: index std::endl; }