欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

[笔记]二分查找的几种写法

程序员文章站 2024-03-20 10:21:04
...

基本形式

  • leftright均为索引值
  • 循环条件:left <= right
  • 向左查找:right = mid-1
  • 向右查找:left = mid+1
  • 查找条件可以在不与元素的两侧进行比较的情况下确定
int binarySearch(vector<int>& nums, int target){
  if(nums.size() == 0)
    return -1;

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

  // End Condition: left > right
  return -1;
}

需要访问右邻居

  • 初始条件:left为索引值, right为索引值+1
  • 循环条件:left < right
  • 向左查找:right = mid
  • 向右查找:left = mid+1
  • 可以访问右邻居mid+1,因为查找空间在每一步中至少有2个元素
  • 需要进行后处理。当你剩下 1 个元素时,循环 / 递归结束。 需要评估剩余元素是否符合条件。
int binarySearch(vector<int>& nums, int target){
  if(nums.size() == 0)
    return -1;

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

  // Post-processing:
  // End Condition: left == right
  if(left != nums.size() && nums[left] == target) return left;
  return -1;
}

需要访问左右邻居

  • 初始条件:leftright均为索引值
  • 循环条件:left + 1 < right
  • 向左查找:right = mid
  • 向右查找:left = mid
  • 可以访问左右邻居,因为查找空间在每一步中至少有3个元素
  • 需要进行后处理。当你剩下 1 个元素时,循环 / 递归结束。 需要评估剩余元素是否符合条件。
int binarySearch(vector<int>& nums, int target){
    if (nums.size() == 0)
        return -1;

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

    // Post-processing:
    // End Condition: left + 1 == right
    if(nums[left] == target) return left;
    if(nums[right] == target) return right;
    return -1;
}

C++中的二分查找

std::lower_bound(arr.begin(), arr.end(), target) 返回首个不小于target的元素的迭代器
std::upper_bound(arr.begin(), arr.end(), target) 返回首个大于target的元素的迭代器

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
 
int main()
{
    std::vector<int> data = { 1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6 };
 
    auto lower = std::lower_bound(data.begin(), data.end(), 4);
    auto upper = std::upper_bound(data.begin(), data.end(), 4);
 
    std::copy(lower, upper, std::ostream_iterator<int>(std::cout, " ")); // 4 4 4
}

参考

探索二分查找 - 力扣 (LeetCode)