二分查找

LeetCode704 二分查找

给定一个 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]之间。

解析

最基础的二分查找了，直接上代码

解答

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

};

LeetCode34 在排序数组中查找元素的第一个和最后一个位置

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例1

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

示例2

输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

示例3

输入：nums = [], target = 0
输出：[-1,-1]

提示：

• \[0 <= nums.length <= 10^5\]
• \[-10^9 <= nums[i] <= 10^9\]
• \[nums是一个非递减数组\]
• \[10^9<= target <= 10^9\]

解析

这是一种特殊的二分查找，就是说在存在同样的值的情况下，我们可以通过收束条件来获得最左端或者最右端的地址。

解答

class Solution {
public:
    int left_bound(vector<int> &nums, int target){
    int l = 0, r = nums.size() - 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{
            //收缩右边区间
            r = mid - 1;
        }
    }
    if (l >= nums.size() || nums[l] != target){
        return -1;
    }
    return l;
}

int right_bound(vector<int> &nums, int target){
    int l = 0, r = nums.size() - 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{
            //收缩左边区间
            l = mid + 1;
        }
    }
    if (r < 0 || nums[r] != target){
        return -1;
    }
    return r;
}
vector<int> searchRange(vector<int>& nums, int target) {
    return vector<int> {left_bound(nums, target), right_bound(nums, target)};
}


};