【Leetcode-704】Binary Search（二分查找）

Github：Leetcode-704. Binary Search(代码实现)

Leetcode-704. Binary Search

Leetcode-704. 二分查找

在元素不重复的升序数组 nums 中查找目标值 target 的下标并返回，如果查不到，返回 -1，

要求时间复杂度必须为 O(log n)。

普通的二分查找，每次取中间值 mid 与目标值 target 比较：

1、如果 mid == target，则返回下标；

2、如果 mid > target，说明查找目标值只可能存在于中间值的左边数组部分，把左边部分

当成新数组，继续取中间值比较；

3、如果 mid < target，说明查找目标值只可能存在于中间值的右边数组部分，把右边部分

当成新数组，继续取中间值比较；

可以使用循环实现，也可以使用递归实现，循环和递归之间的实现逻辑是可以相互转换的。

package com.jpeony.leetcode.n0704;


public class N704_BinarySearch {

    
    private static int search(int[] nums, int target) {
        // 低位
        int low = 0;
        // 高位
        int high = nums.length - 1;
        // 注意，这里是 low <= high，不是 low < high
        while (low <= high) {
            // 中间值
            int mid = low + (high - low) / 2;
            // 中间值等于目标值
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] > target) {// 中间值大于目标值，左侧查找
                high = mid - 1;
            } else {// 中间值小于目标值，右侧查找
                low = mid + 1;
            }
        }
        // 在数组中未找到目标值，返回 -1
        return -1;
    }

    public static void main(String[] args) {
        int[] nums = {-1, 0, 3, 5, 9, 12};
        int target = 9;
        int targetIndex = search(nums, target);
        System.out.println("targetIndex = " + targetIndex);
    }
}

时间复杂度：O(log n)。二分查找每次都是二分治折半查找，所以时间复杂度为 O(log n)。

空间复杂度：O(1)。只是用了临时变量 mid，所以空间复杂度为 O(1)。