[LeetCode] 704. Binary Search

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.

Example 1:
Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4

Example 2:
Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1

Constraints:
1 <= nums.length <= 104
-104 < nums[i], target < 104
All the integers in nums are unique.
nums is sorted in ascending order.

二分查找。

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-search
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

这个题跟35题几乎一样。思路就是二分，没什么可说的，但是注意二分查找有好几种模板，我这里给出我比较喜欢的一种。当while条件是带等号的时候，且当nums[mid] < target的时候，因为知道mid及其左边都小于target，所以left可以从mid的右边（mid + 1）开始继续查找，同理right也是从mid的左边开始查找，即right = mid - 1。

同时我解释一下 while (left <= right) 的终止条件是 left == right + 1，写成区间的形式就是 [right + 1, right]，或者带个具体的数字进去 [3, 2]，可见这时候区间为空，因为没有数字既大于等于 3 又小于等于 2 的吧。所以这时候 while 循环终止是正确的，直接返回 -1 即可。

复杂度

时间O(logn)
空间O(1)

代码

Java实现一

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        // 注意right的定义，是数字的最后一个元素的下标
        int right = nums.length - 1;

        // 搜索的范围都在数组的下标范围内
        // 如果nums[mid]不是目标值，下标一定要 +/- 1
        // 注意left <= right
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }
}

Java实现二

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        // 注意right的定义，是数字的最后一个元素的下标
        int right = nums.length - 1;

        // 搜索的范围都在数组的下标范围内
        // 如果nums[mid]不是目标值，下标一定要 +/- 1
        // 注意left <= right
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }
}

Java实现三

class Solution {
    public int search(int[] nums, int target) {
        int start = 0;
        int end = nums.length - 1;
        // 因为 start + 1 < end，当跳出while循环的时候，start + 1 = end，start 和 end 是相邻的坐标，所以有最后的特判
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] > target) {
                end = mid;
            } else {
                start = mid;
            }
        }
        if (nums[start] == target) {
            return start;
        }
        if (nums[end] == target) {
            return end;
        }
        return -1;
    }
}

JavaScript实现

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {
    // corner case
    if (nums == null || nums.length == 0) {
        return -1;
    }

    // normal case
    let left = 0;
    let right = nums.length - 1;
    while (left <= right) {
        let mid = Math.floor(left + (right - left) / 2);
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
};

相关题目

35. Search Insert Position
704. Binary Search