二分法排序

二分查找（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 = 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; // 沒有找到
}

五、應用場景

二分法排序最常用的應用場景是在數組中查找元素。除此之外，二分法排序還可以用於一些其他的問題，例如求開方、最大值（最小值）等。