当你需要在一个有序数组中查找特定元素时，二分查找是一种高效的算法。它的时间复杂度为 O(log n)，相较于线性查找的 O(n)，二分查找可以显著提高搜索效率。本文将详细解释什么是二分查找，以及如何在 Java 中实现它。
二分查找简介
二分查找，也称为折半查找，是一种在有序数组中查找目标元素的算法。它的原理是不断将查找范围减半，直到找到目标元素或确定目标元素不存在。二分查找的步骤如下：
- 初始化左边界 left 为数组第一个元素的索引，右边界 right 为数组最后一个元素的索引。
- 计算中间元素的索引 mid，它等于 (left + right) / 2。
- 比较中间元素与目标元素：
- 如果中间元素等于目标元素，则找到目标，返回中间元素的索引。
- 如果中间元素大于目标元素，则将右边界更新为 mid - 1，继续在左半边查找。
- 如果中间元素小于目标元素，则将左边界更新为 mid + 1，继续在右半边查找。
- 重复步骤 2 和 3，直到找到目标元素或左边界超过右边界。
Java 实现二分查找
以下是在 Java 中实现二分查找的示例代码：
/**
* 二分查找
*/
public static int binarySearch(int[] intArr,int key){
int left = 0;
int right = intArr.length -1;
while(left <= right){
//计算中间元素的索引
int mid = (left + right) >>> 1;
//获取中间元素的值
int midVal = intArr[mid];
//比较中间元素和目标元素的值
//如果中间元素小于目标元素，则将左边界更新为 mid + 1，继续在右半边查找。
if (midVal < key)
left = mid + 1;
//如果中间元素大于目标元素，则将右边界更新为 mid - 1，继续在左半边查找。
else if (midVal > key)
right = mid - 1;
//如果中间元素等于目标元素，则找到目标，返回中间元素的索引。
else
return mid;
}
//如果循环结束仍未找到目标元素，返回一个负数，表示未找到，通常为-(left + 1)
return -(left + 1);
}
public static void main(String[] args) {
int[] intArray = new int[]{
2,4,5,7,9,11,16,23,45,67};
System.out.println(binarySearch(intArray,5));
System.out.println(binarySearch(intArray,23));
System.out.println(binarySearch(intArray,1));
System.out.println(binarySearch(intArray,20));
System.out.println(binarySearch(intArray,110));
}
输出结果为：
2
7
-1
-8
-11
上述代码中，binarySearch 方法接受一个有序数组 intArr 和目标元素 key 作为参数，然后使用二分查找算法在数组中查找目标元素的索引。如果找到目标元素，返回它的索引；否则，返回 负数 表示目标元素不存在。
注意事项
二分查找的前提是数组必须是有序的，否则无法正常工作。如果数组不是有序的，需要先对数组进行排序，然后才能使用二分查找算法。
总结
二分查找是一种高效的查找算法，适用于有序数组。它的时间复杂度为 O(log n)，其中 n 是数组的长度。由于每次迭代都将搜索范围减半，因此它比线性查找等简单查找算法更加高效，特别是对于大型有序数组。通过仔细实现和理解二分查找算法，你可以在 Java 中轻松应用它来解决各种查找问题。
