Leetcode|基本二分搜索+左侧边界二分+右侧边界二分

SL_World

发布于 2021-09-18 08:52:25

1.9K00

代码可运行

文章被收录于专栏：XX

运行总次数：0

代码可运行

文章目录

1 基本二分搜索

【区间】：[left, right]

【终止条件】：left = right + 1

int binarySearch(vector<int>& nums, int target) {
    // 区间[left, right]
    int left = 0, right = nums.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target)
            return mid;
        else if (nums[mid] < target)
            left = mid + 1;
        else if (nums[mid] > target)
            right = mid - 1;
    }
    return -1;
}

2 左侧边界二分

【区间】：[left, right)

【终止条件】：left = right

/**寻找左侧边界的二分搜索**/
int leftBound(vector<int>& nums, int target) {
    // 区间[left, right)
    int left = 0, right = nums.size();
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target)
            // 不返回，收缩右边界，找到左侧边界
            right = mid;
        else if (nums[mid] < target)
            left = mid + 1;
        else if (nums[mid] > target)
            right = mid;
    }
    if (left == nums.size()) return -1;
    return nums[left] == target ? left : -1;
}

3 右侧边界二分

【区间】：[left, right)

【注意】：最后是mid = left - 1

【终止条件】：left = right

/**寻找右侧边界的二分搜索**/
int rightBound(vector<int>& nums, int target) {
    // 区间[left, right)
    int left = 0, right = nums.size();
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target)
            // 不返回，收缩左边界，找到左右侧边界
            left = mid + 1;
        else if (nums[mid] < target)
            left = mid + 1;
        else if (nums[mid] > target)
            right = mid;
    }
    if (left == 0) return -1;
    return nums[left - 1] == target ? left - 1 : -1;
}