704.二分查找

【LetMeFly】704.二分查找

力扣题目链接：https://leetcode.cn/problems/binary-search/

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

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

 

提示：

1. 你可以假设 nums 中的所有元素是不重复的。
2. n 将在 [1, 10000]之间。
3. nums 的每个元素都将在 [-9999, 9999]之间。

方法一：二分查找

二分查找主要有两种写法：对于区间$l$到$r$，采用闭区间还是左闭右开区间。

关于二分查找过程中：

• while (l < r)还是while (l <= r)的关键是：保证while过程中区间不空
• r = mid还是r = mid - 1的关键是：判定过的元素坚决不留在区间内

以C++ lower_bound等左闭右开的二分方法为例：

数组$nums$的有效范围是$[0, n - 1]$，则初始值令$l = 0, r = n$（左闭右开）。

在循环过程中，保证区间不空，则需要$r > l$（因为如果$l$等于$r$，则因左闭右开区间已经空了）

若$nums[mid] > target$，则$mid$已经被排除了，下次的区间中不应包含$mid$，因此令$r = mid$（右边是开区间，取不到）

while (l < r) {  // [l, r)不空
    int mid = (l + r) / 2;
    if (nums[mid] > target) r = mid;  // 新区间[l, mid)
    if (nums[mid] < target) l = mid + 1;  // 新区间[mid + 1, r)
    if (nums[mid] == target) return mid;
}

同理，若以闭区间的方法来写：

初始值$l = 0, r = n - 1$

while (l <= r) {  // [l, r]不空
    int mid = (l + r) / 2;
    if (nums[mid] > target) r = mid - 1;  // 新区间[l, mid - 1]
    if (nums[mid] < target) l = mid + 1;  // 新区间[mid + 1, r]
    if (nums[mid] == target) return mid;
}

• 时间复杂度$O(\log len(nums))$
• 空间复杂度$O(1)$

AC代码

C++

左闭右开：

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l = 0, r = nums.size();
        while (l < r) {
            int mid = (l + r) >> 1;
            if (nums[mid] > target) {
                r = mid;
            }
            else if (nums[mid] < target) {
                l = mid + 1;
            }
            else {
                return mid;
            }
        }
        return -1;
    }
};

闭区间：

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l = 0, r = nums.size() - 1;
        while (l <= r) {
        int mid = (l + r) / 2;
        if (nums[mid] > target) r = mid - 1;
        if (nums[mid] < target) l = mid + 1;
        if (nums[mid] == target) return mid;
    }
        return -1;
    }
};

Python

左闭右开：

# from typing import List

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums)
        while l < r:
            mid = (l + r) // 2
            if nums[mid] > target:
                r = mid
            elif nums[mid] < target:
                l = mid + 1
            else:
                return mid
        return -1

闭区间：

# from typing import List

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums) - 1
        while l <= r:
            mid = (l + r) // 2
            if nums[mid] > target:
                r = mid - 1
            elif nums[mid] == target:
                return mid
            else:
                l = mid + 1
        return -1

同步发文于CSDN，原创不易，转载经作者同意后请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/133610614