2022-06-07 3-1 二分查找

力扣题目：Link

二分法前提条件：

1. 有序——符合二分法的逻辑
2. 去重——防止返回的 index 不唯一

二分法两种写法的关键：

两种写法的不同点在于 target 在闭区间还是左闭右开。

1. while(left < right) 在 [left, right] 区间内是否有效；
2. nums[middle] > right 时，实际比较的是 nums[middle] 还是 nums[middle-1] 。

二分法Pseudocode：

BINARY-SEARCH (array arr, int index) 
    left = 0;
    right = arr.size();
    while (left < right) {
        int middle = left + ((right - left) / 2);
        if (arr[middle] > target) {
            right = middle;
        } else if (arrr[middle] < target) {
            left = middle;
        } else {
            return middle;
        }
    }
    return -1;