C++数据结构--二分搜索

一.什么是二分搜索二分搜索Binary Search是一种在有序数组中查找特定元素的高效算法。二分搜索算法,实际上就是对一颗BST树从root根节点开始搜索的过程,每一次搜索只会沿着一条路径搜索下去核心思想:是每次定义索引left与right每次找一个mid比较mid索引的值与应找值val之后缩小查找范围循环操作直到找到val或者循环结束。二.非递归代码实现非递归实现二分搜索借助循环直到left小于等于right循环结束。int BinarySearch(int arr[], int size, int val)//二分搜索非递归 { int left 0; int right size - 1; int middle (left right)/2; while (left right) { if (val arr[middle]) { return middle; } else if (val arr[middle]) { right middle - 1; middle (left right) / 2; } else { left middle 1; middle (left right) / 2; } } return -1; }三.递归代码实现递归代码实现借助递归代替循环核心思路相同。二分搜索递归 int BinarySearch(int arr[], int val,int i,int j) { int mid (i j) / 2; if (i j) { return -1; } else if(valarr[mid]) { return BinarySearch(arr, val, i, mid - 1); } else if (val arr[mid]) { return BinarySearch(arr, val, mid1, j); } else if (val arr[mid]) { return mid; } }四.二分搜索的时间复杂度由于二分搜索实际上是对BST树从root根节点开始搜索的过程所以二分搜索的平均时间复杂度为logn。空间复杂度为O(n)。