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(val<arr[mid]) { return BinarySearch(arr, val, i, mid - 1); } else if (val > arr[mid]) { return BinarySearch(arr, val, mid+1, j); } else if (val == arr[mid]) { return mid; } }

四.二分搜索的时间复杂度

由于二分搜索实际上是对BST树，从root根节点开始搜索的过程，所以二分搜索的平均时间复杂度为logn。空间复杂度为O(n)。