二分搜索算方

二分搜索是一种在排序或单调搜索空间上运行的搜索算法，通过反复将其分割成两半，以在对数时间O（log N）内找到目标值或最优答案。

在数据结构中应用二分搜索算法的条件
应用二分搜索算法：

数据结构必须被排序。
访问数据结构的任何元素应耗时为常数。
二叉搜索算法
以下是二分搜索的逐步算法：

通过找到中间的索引“mid”，将搜索空间分成两半。
比较搜索空间的中间元素与键。
如果 密钥位于中间元素，则进程终止。
如果中间元素找不到关键，选择下一个搜索空间的一半。
-> 如果键比中间元素小，则下一次搜索使用左侧。
-> 如果键大于中间元素，则下一次搜索使用右侧。
该过程持续进行，直到找到关键密钥或整个搜索空间耗尽。
二分搜索算法是如何工作的？
为了理解二分搜索的工作原理，请考虑以下示例：

考虑数组 arr[] = {2， 5， 8， 12， 16， 23， 38， 56， 72， 91}，目标 = 23。

如何实现二分搜索？
二叉搜索算法可以通过以下两种方式实现

迭代二分搜索算法
递归二分搜索算法
迭代算法：时间 O（log n） 和空间 O（1）
这里我们使用while循环继续比较密钥并将搜索空间分成两半的过程。

重定向图标

class GFG { static int binarySearch(int arr[], int x) { int low = 0, high = arr.length - 1; while (low <= high) { int mid = low + (high - low) / 2; // Check if x is present at mid if (arr[mid] == x) return mid; // If x greater, ignore left half if (arr[mid] < x) low = mid + 1; // If x is smaller, ignore right half else high = mid - 1; } // If we reach here, then element was // not present return -1; } public static void main(String args[]) { int arr[] = { 2, 3, 4, 10, 40 }; int x = 10; int result = binarySearch(arr, x); if (result == -1) System.out.println( "Element is not present in array"); else System.out.println("Element is present at " + "index " + result); } }

输出
Element is present at index 3
递归算法：时间 O（log n） 和空间 O（log n）
创建一个递归函数，并将搜索空间的中间值与键进行比较。根据结果，要么返回找到密钥的索引，要么调用下一个搜索空间的递归函数。

class GFG { // A recursive binary search function. It returns // location of x in given array arr[low..high] is present, // otherwise -1 static int binarySearch(int arr[], int low, int high, int x) { if (high >= low) { int mid = low + (high - low) / 2; // If the element is present at the // middle itself if (arr[mid] == x) return mid; // If element is smaller than mid, then // it can only be present in left subarray if (arr[mid] > x) return binarySearch(arr, low, mid - 1, x); // Else the element can only be present // in right subarray return binarySearch(arr, mid + 1, high, x); } // We reach here when element is not present // in array return -1; } public static void main(String args[]) { int arr[] = { 2, 3, 4, 10, 40 }; int n = arr.length; int x = 10; int result = binarySearch(arr, 0, n - 1, x); if (result == -1) System.out.println( "Element is not present in array"); else System.out.println( "Element is present at index " + result); } }

输出
Element is present at index 3
复杂性分析
时间复杂度：
-> 最佳情况：O（1）
-> 平均情况：O（对数n）
->最坏情况：O（log n）
辅助空间：O（1），如果考虑递归调用栈，则辅助空间为 O（log N）。

编程资源 https://pan.quark.cn/s/7f7c83756948 更多资源 https://pan.quark.cn/s/bda57957c548