介绍

二分查找（Binary Search）是一种在有序数组中查找特定元素的搜索算法。其基本思想是将目标值与数组中间的元素进行比较：

1. 如果目标值等于中间元素，则查找成功。
2. 如果目标值小于中间元素，则在数组左半部分继续进行二分查找。
3. 如果目标值大于中间元素，则在数组右半部分继续进行二分查找。

这个过程将不断重复，直到找到目标值或搜索范围为空为止。

实现步骤

下面是二分查找算法的一般步骤：

1. 初始化两个指针，一个指向数组的起始位置（low），另一个指向数组的结束位置（high）。
2. 计算中间位置（mid）：mid=⌊(low+high)/2⌋mid=⌊(low+high)/2⌋
3. 比较中间元素与目标值：
   • 如果中间元素等于目标值，返回中间位置。
   • 如果中间元素大于目标值，将high更新为mid - 1。
   • 如果中间元素小于目标值，将low更新为mid + 1。
4. 重复步骤2和3，直到找到目标值或low大于high为止。

如果最终low大于high，表示目标值不在数组中，可以返回一个表示未找到的值，比如-1。

二分查找的时间复杂度是O(log n)，其中n是数组的大小。这使得它在处理大型数据集时非常高效。然而，二分查找要求数组必须是有序的，这是它的一个限制条件。

代码实现

public class BinarySearch {public static void main(String[] args) {// 初始化一个有序数组int[] arr = {1, 8, 10, 34, 44, 46, 56, 59, 61, 63, 66, 68, 69, 70, 89, 1000, 1234};// 使用递归版本查找目标值89在数组中的索引int index = binarySearch(arr, 0, arr.length - 1, 89);// 使用循环版本查找目标值89在数组中的索引int index1 = binarySearch(arr, 89);// 打印两个版本的查找结果System.out.println(index + " " + index1);}// 递归版本的二分查找算法private static int binarySearch(int[] arr, int left, int right, int target) {// 基本情况：如果left大于right，说明target不在数组中，返回-1if(left > right) {return -1;}// 计算中间索引int mid = (left + right) / 2;// 如果中间元素等于目标值，返回中间索引if(arr[mid] == target) {return mid;} else if(arr[mid] > target) {// 如果中间元素大于目标值，在左半部分递归调用二分查找return binarySearch(arr, left, mid - 1, target);} else {// 如果中间元素小于目标值，在右半部分递归调用二分查找return binarySearch(arr, mid + 1, right, target);}}// 循环版本的二分查找算法private static int binarySearch(int[] arr, int target) {// 初始化左右指针int left = 0;int right = arr.length - 1;// 当left小于等于right时，继续循环while(left <= right) {// 计算中间索引int mid = (left + right) / 2;// 如果中间元素等于目标值，返回中间索引if(arr[mid] == target) {return mid;} else if(arr[mid] > target) {// 如果中间元素大于目标值，更新right为mid-1right = mid - 1;} else {// 如果中间元素小于目标值，更新left为mid+1left = mid + 1;}}// 如果没有找到目标值，返回-1return -1;}
}

测试结果

产生问题

在二分查找算法中，计算中间索引 mid 的表达式 int mid = (left + right) / 2; 可能会在某些情况下导致问题。具体来说，如果 left 和 right 是非常大的整数，那么它们的和可能会超出 int 类型所能表示的范围，导致整数溢出。

整数溢出会导致 mid 的值不正确，这可能会使二分查找算法无法正确执行，甚至进入无限循环。

举例说明

解决问题

使用位运算： 使用位运算来避免溢出，因为位运算是按位进行的，不会导致溢出。计算 mid 的表达式如下： 

mid=left + (( right − left )  >> 1 )

这里，>> 是右移位运算符，它将 right - left 的二进制表示向右移动一位，相当于除以2。

使用这些方法可以确保在执行二分查找时 mid 的值是正确的，从而避免因整数溢出导致的问题

修改代码

 // 递归版本private static int binarySearch(int[] arr, int left, int right, int target) {if(left > right) {return -1;}// int mid = (left + right)/2;int mid = left + ((right - left) >> 1);if(arr[mid] == target) {return mid;} else if(arr[mid] > target) {return binarySearch(arr, left, mid - 1, target);} else {return binarySearch(arr, mid + 1, right, target);}}// 循环版本private static int binarySearch(int[] arr, int target) {int left = 0;int right = arr.length - 1;while(left <= right) {//int mid = (left + right)/2;int mid = left + ((right - left) >> 1);if(arr[mid] == target) {return mid;} else if(arr[mid] > target) {right = mid - 1;} else {left = mid + 1;}}return -1;}

测试结果