二分查找

都以左闭右闭的方式，即

int l = 0, r = nums.length - 1;
while (l <= r)

基本二分查找

int binarySearch(int[] nums, int target) {
        // 设置左右边界
        int l = 0, r = nums.length - 1; 
        while (l <= r) {
            int mid = l + (r - l) / 2; // 等同于mid=(l+r)/2,这种写法是为了防止数组越界,也可以写为(l+r) >>> 1
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                l = mid + 1;
            } else if { 
                r = mid - 1;
            }
        }
        // 最后判断: l>r 即数组不存在
        return -1;
    }

寻找左侧边界的二分查找

int left_bound(int[] nums, int target) {
    int l = 0, r = nums.length - 1;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (nums[mid] < target) {
            l = mid + 1;
        } else if (nums[mid] > target) {
            r = mid - 1;
        } else if (nums[mid] == target) { 
            // 收缩右侧边界
            r = mid - 1;            
        }
    }
    // 判断 target 是否存在于 nums 中
    // 如果越界，target 肯定不存在，返回 -1
    if (l < 0 || l >= nums.length) {
        return -1;
    }
    // 判断一下 nums[l] 是不是 target
    return nums[l] == target ? l : -1;
}

寻找右侧边界的二分查找

int right_bound(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] == target) {
                l = mid + 1;
            } else if (nums[mid] < target) {
                l = mid + 1;
            } else if (nums[mid] > target) {
                r = mid - 1;
            }
        }
        if (r < 0 || r >= nums.length) {
            return -1;
        }

        return nums[r] == target ? r : -1;
    }

完整测试

public class binary {

    int binarySearch(int[] nums, int target) {
        // 设置左右边界
        int l = 0, r = nums.length - 1; 
        while (l <= r) {
            int mid = l + (r - l) / 2; // 等同于mid=(l+r)/2,这种写法是为了防止数组越界,也可以写为(l+r) >>> 1
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                l = mid + 1;
            } else if { 
                r = mid - 1;
            }
        }
        // 最后判断: l>r 即数组不存在
        return -1;
    }
    
    
    public static int left_bound(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] == target) {
                // 收缩右侧边界
                r = mid - 1;
            } else if (nums[mid] > target) {
                r = mid - 1;
            } else if (nums[mid] < target) {
                l = mid + 1;
            }
        }
        // 判断 target 是否存在于 nums 中
        // 如果越界，target 肯定不存在，返回 -1
        if (l < 0 || l >= nums.length) {
            return -1;
        }
        // 判断一下 nums[l] 是不是 target
        return nums[l] == target ? l : -1;
    }


    public static int right_bound(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] == target) {
                l = mid + 1;
            } else if (nums[mid] < target) {
                l = mid + 1;
            } else if (nums[mid] > target) {
                r = mid - 1;
            }
        }
        if (r < 0 || r >= nums.length) {
            return -1;
        }

        return nums[r] == target ? r : -1;
    }


    public static void main(String[] args) throws Exception {
        int[] arr = {1, 2, 2, 2, 2, 2, 7, 8};
        //int index = binarySearch(arr, 2);
        //int index = left_bound(arr, 2);
        int index = right_bound(arr, 2);
        System.out.println(index);
    }
}

查找应用

局部最小

规定：边界arr[0]<arr[1]，arr[0]即为局部最小，arr[n-1]<arr[n-2]，则arr[n-1]局部最小，中间的数arr[i-1]<arr[i]<arr[i+1]，则arr[i]为局部最小。

问题：一个无序数组，查找局部最小，O(logn)复杂度

若边界都不是局部最小，则中间必有局部最小，取中间位置，若m-1<m则0~m必有局部最小，一直二分下去就能找到。

查找算法