二分查找（Binary Search）

二分查找（Binary Search），是一种在有序数组中查找某一特定元素的搜索算法。二分查找的思想类似于分治思想。

一、基本思想

实现二分法排序，首先要明确基本思想，即：在有序数组中，每次取数组的中间位置，如果该位置上的值不是要查找的值，继续在大于或者小于它的那一半中查找，直到查找到目标为止。

int binarySearch(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1; // 没有找到
}

二、时间复杂度

二分法排序的时间复杂度为 O(log n)。因为每次都会将数组缩小一半，在最坏的情况下，需要进行 log n 次操作才能找到目标元素。

三、适用条件

二分法排序仅适用于有序数组。在无序数组中查找元素，需要先将数组排序再进行查找。

四、如何处理重复元素

有时候数组中可能会有重复的元素，怎么办呢？ 一种方法是，在查找到目标元素的时候，向前或向后遍历，查找其他相同的元素。这种方法的时间复杂度为 O(k)，其中 k 为相同元素的个数，因此效率较低。

int binarySearch(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (arr[mid] == target) {
            // 查找其他相同的元素
            int i = mid - 1;
            while (i >= 0 && arr[i] == target) { i--; }
            int j = mid + 1;
            while (j < arr.length && arr[j] == target) { j++; }
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1; // 没有找到
}

另一种方法是，在进行比较的时候，判断中间值是否包含在目标区间内。

int binarySearch(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;
    while (left <= right) {
        int mid = (left + right) / 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; // 没有找到
}

五、应用场景

二分法排序最常用的应用场景是在数组中查找元素。除此之外，二分法排序还可以用于一些其他的问题，例如求开方、最大值（最小值）等。