圈圈小站

quanquan's blog

0%

二分搜索总结 BinarySearch

发表于

二分搜索几种情况总结以及例题分享。

  • 不重复元素寻找目标值（最基本）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//找不到返回-1
int search(vector<int>& nums, int target) {
        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)
                right = mid-1;
            else
                left = mid+1;
        }
        return -1;
    }

该模板的应用：

1.leetcode——x的平方根

2.leetcode——猜数字大小

3.leetcode——搜索旋转排序数组 有点妙！题解：leetcode题解C++

  • 找当前索引以及直接右邻索引

1
2
3
4
5
6
7
8
9
10
11
12
13
int binarySearch(vector<int>& nums, int target){
  if(nums.size() == 0)
    return -1;

  int left = 0, right = nums.size();
  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; }
  }
  return left;
}

该模板的应用：

1.leetcode——第一个错误的版本

2.leetcode——寻找峰值

3.leetcode——寻找旋转排序数组中的最小值

4.leetcode——找到k个最接近的元素 很妙的思路！

  • 找当前索引以及直接左右邻索引

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int binarySearch(vector<int>& nums, int target){
    if (nums.size() == 0)
        return -1;

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

    if(nums[left] == target) return left;
    if(nums[right] == target) return right;
    return -1;
}

  • 找元素出现的第一个位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//若没找到，返回大于该元素的第一个元素
int lowerBound(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);  //不容易移除
            if (target <= nums[mid]) {
                //当目标值小于等于nums[mid]时，继续在左区间检索，找到第一个数
                right = mid - 1;

            }else if (target > nums[mid]) {
                //目标值大于nums[mid]时，则在右区间继续检索，找到第一个等于目标值的数
                left = mid + 1;
            }
        }
        return left;
    }

  • 找元素出现的最后一个位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//若没找到，返回小于该元素的第一个元素
int upperBound(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            //移动左指针情况
            if (target >= nums[mid]) {
                 left = mid + 1; 
            //移动右指针情况
            }else if (target < nums[mid]) {
                right = mid - 1;
            }
            
        }
        return right;
    }

相关题目：

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