二分查找

发表于 | Edited on | 分类于

二分查找

二分查找是计算机科学中最基本、最有用的算法之一。它描述了在有序集合中搜索特定值的过程。

二分查找中使用的术语：

  • 目标Target–你要查找的值
  • 索引Index–你要查找的当前位置
  • 左、右指示符Left、Right–用来维持查找空间的指标
  • 中间指示符Mid–我们用来应用条件来确定我们应该向左查找还是向右查找的索引

如何工作

二分查找对具有指定左索引和右索引的连续序列进行操作。这就是所谓的查找空间。二分查找维护查找空间的左、右和中间指示符，并比较查找目标或将查找条件应用于集合的中间值；如果条件不满足或值不相等，则清除目标不可能存在的那一半，并在剩下的一半上继续查找，直到成功为止。如果查以空的一半结束，则无法满足条件，并且无法找到目标。

二分查找

寻找左侧边界的二分搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int left_bound(int[] nums, int target) {
    if (nums.length == ) return -1;
    int left = 0;
    int right = nums.length;
    while(left < right) {//因为搜索区间是左闭右开
        int mid = (left + right) / 2;
        if (nums[mid] == target) {
            right = mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid;
        }
    }
    return left;

猜测数字大小

搜索旋转排序数组

  • 找到选择的下标rotation_index，也就是数组中最小的元素。二分查找在这里可以派上用上。
  • 在选中的数组区域中再次使用二分查找
0%