关于二分法查找Java的实现及解析

什么是二分法查找

二分查找是一种非常高效的查找算法，也叫折半查找。它是在一个有序的数组中查找指定目标值的位置，它的算法思路是每次取数组的中间元素和目标值比较，通过二分的方式不断缩小查找范围，直到找到目标值为止。

Java实现二分法查找

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

代码解析：

1. 设置左边界为0，右边界为数组长度减1，表示查找范围是整个数组。
2. 当左边界小于等于右边界时，循环继续执行。
3. 取当前查找范围中间位置的元素，和目标值比较。
4. 如果中间元素等于目标值，则直接返回中间位置。
5. 如果中间元素小于目标值，则目标值在中间元素的右边，将左指针设置为中间位置的右边。
6. 如果中间元素大于目标值，则目标值在中间元素的左边，将右指针设置为中间位置的左边。
7. 如果最后没找到，返回-1表示未找到。

代码示例

我们来看一个实际的例子：从一个有序数组中查找目标值为6的元素。

int[] nums = {1, 3, 5, 6, 7, 9, 10};
int target = 6;
int index = binarySearch(nums, target);
System.out.println(index);

运行结果为3，表示目标值为6的元素在数组中的索引位置是3。

这里再来一个复杂些的例子：从一个有序数组中查找目标值为8的元素。

int[] nums = {1, 2, 3, 5, 6, 8, 9, 10};
int target = 8;
int index = binarySearch(nums, target);
System.out.println(index);

运行结果为5，表示目标值为8的元素在数组中的索引位置是5。

总结

二分法查找是一种非常高效的查找算法，时间复杂度为O(log n)，它需要有序数组作为输入，对于有序数组可以用这种算法快速查找目标元素。Java实现二分查找算法的代码很简单，需要注意的是左指针和右指针的初始化和更新条件。