java二分查找算法详解

二分查找遵循分治策略，在升序排列的有序数组中查找元素。核心是反复减半搜索区间，先确定中间元素并与目标元素比较，若相等则查找成功返回其索引；若中间元素大于目标元素，就把搜索区间缩小到左半部分（更新右边界）；若小于，则缩小到右半部分（更新左边界）。如此重复，直至找到目标元素或确定其不存在（左边界大于右边界时）。

例如数组 [1, 3, 5, 7, 9, 11, 13, 15]，找7时中间元素就是7（索引3），能直接找到；找6时，因中间元素7大于6，就将搜索区间缩小至 [1, 3, 5] 继续重复操作，直至确定6不在数组中。

java 代码实现

java">public class Main {public static int binarySearch(int[] arr, int target) {int left = 0;int right = arr.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (arr[mid] == target) {return mid;} else if (arr[mid] < target) {left = mid + 1;} else {right = mid - 1;}}return -1;}public static void main(String[] args) {int[] arr = {1,2,3,4,5,6,7,8,9};int target = 9;int result = binarySearch(arr, target);if (result == -1) {System.out.println("目标元素未找到");} else {System.out.println("目标元素在索引 " + result + " 处");}}
}

在上述代码中， left 和 right 分别表示当前搜索区间的左右边界，通过循环不断调整这两个边界，直到找到目标元素或者 left 大于 right 。

*在计算中间索引 mid 时，使用 left + (right - left) / 2 而不是 (left + right) / 2 是为了防止在 left 和 right 很大时出现整数溢出的情况。

时间复杂度

二分查找的时间复杂度为O(log n)，其中 n 是数组的长度，这是因为每次迭代都将搜索区间减半。在最坏的情况下，直到搜索区间缩小到只剩下一个元素才确定目标元素是否存在，需要进行log_2 n次比较。

二分查找的变体

在某些情况下，我们不仅要找到目标元素，还希望找到它在数组中第一次出现的位置。例如，在数组 [1, 2, 3, 4, 5, 6, 7, 8, 9, 9] 中查找 9，我们希望返回索引 8 而不是 9。

需要将代码改成：

java"> public static int binarySearch(int[] arr, int target) {int left = 0;int right = arr.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (arr[mid] == target) {if (mid == 0 || arr[mid - 1]!= target) {return mid;} else {right = mid - 1;}} else if (arr[mid] < target) {left = mid + 1;} else {right = mid - 1;}}return -1;}

当找到目标元素后，我们还需要检查它是否是第一个出现的，如果当前索引为 0 或者前一个元素不等于目标元素，那么就找到了第一个等于目标值的元素，否则继续在左半部分查找。

有时我们需要找到目标元素在数组中最后一次出现的位置，例如，在数组[1, 2, 3, 4, 5, 6, 7, 8, 9, 9] 中查找 9，我们希望返回索引 9。

java">public static int findLastEqual(int[] arr, int target) {int left = 0;int right = arr.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (arr[mid] == target) {if (mid == arr.length - 1 || arr[mid + 1]!= target) {return mid;} else {left = mid + 1;}} else if (arr[mid] < target) {left = mid + 1;} else {right = mid - 1;}}return -1;
}

同理，当找到目标元素后，检查它是否是最后一个出现的，如果当前索引为数组末尾或者后一个元素不等于目标元素，那么就找到了最后一个等于目标值的元素。

查找最后一个满足小于等于目标值条件的元素：

java">public static int findLastLessEqual(int[] arr, int target) {int left = 0;int right = arr.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (arr[mid] <= target) {if (mid == arr.length - 1 || arr[mid + 1] > target) {return mid;} else {left = mid + 1;}} else {right = mid - 1;}}return -1;
}

当找到一个小于等于目标值的元素后，检查它是否是最后一个满足条件的，如果当前索引为数组末尾或者后一个元素大于目标值，那么就找到了最后一个小于等于目标值的元素，否则继续右分查找更大的满足条件的元素。

二分查找的常见错误及注意事项

在实现二分查找时，最常见的错误之一就是边界条件的处理不当。例如，在循环条件中使用 left < right 而不是 left <= right 可能会导致遗漏对最后一个元素的检查。
在计算中间索引 mid 时，如果简单地使用 (left + right) / 2 ，当 left 和 right 都很大时，可能会发生整数溢出。正确的做法是使用 left + (right - left) / 2 来避免这个问题。
二分查找的前提是数组必须是有序的，在使用二分查找之前要确保数组已经按照正确的顺序排序。