算法思路
Source
Edit
History

undefined

二分查找

二分查找的时间复杂度：logn

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool binary_sort(std::vector<int>& vec, int value) {
    int left = 0;
    int right = vec.size()-1;
    while (left <= right) {
        int mid = left + (right - left)/2;
        if (value == vec[mid]) {
            return true;
        } else if (value > vec[mid]) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return false;
}

注意循环条件为：left <= right 以及注意 left + right 越界的情况

一、条件

  1. 二分查找依赖的是顺序表结构，简单点说就是数组
  2. 其次，二分查找针对的是有序数据。
  3. 二分查找的底层需要依赖数组这种数据结构，而数组为了支持随机访问的特性，要求内存空间连续，对内存的要求比较苛刻。比如即使我们有 2G 内存，但是是零散的，没有连续的 1G 的内存空间，想要 1G 大小的数组也不行。
  • 如何在 1000 万个整数中快速查找某个整数？

每个数据大小 8 个字节，1000万个数据大概是80M，存储在数组中，排序后用二分查找即可。如果内存限制100M，其实是不能用散列表或者二叉树的，因为这些数据结构需要额外的数据结构。

题目

  1. 求一个数的平方根？先用二分求整数，在用二分求分位数
  2. 循环有序数组如何使用二分查找？

二分查找的变形

4 中常见的二分查找变形问题

  1. 查找第一个值等于给定值的元素

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    public int bsearch(int[] a, int n, int value) {
      int low = 0;
      int high = n - 1;
      while (low <= high) {
        int mid =  low + ((high - low) >> 1);
        if (a[mid] > value) {
          high = mid - 1;
        } else if (a[mid] < value) {
          low = mid + 1;
        } else {
          if ((mid == 0) || (a[mid - 1] != value)) return mid;
          else high = mid - 1;
        }
      }
      return -1;
    }

  2. 查找最后一个值等于给定值的元素

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    public int bsearch(int[] a, int n, int value) {
      int low = 0;
      int high = n - 1;
      while (low <= high) {
        int mid =  low + ((high - low) >> 1);
        if (a[mid] > value) {
          high = mid - 1;
        } else if (a[mid] < value) {
          low = mid + 1;
        } else {
          if ((mid == n - 1) || (a[mid + 1] != value)) return mid;
          else low = mid + 1;
        }
      }
      return -1;
    }

  3. 查找第一个大于等于给定值的元素

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    public int bsearch(int[] a, int n, int value) {
      int low = 0;
      int high = n - 1;
      while (low <= high) {
        int mid =  low + ((high - low) >> 1);
        if (a[mid] >= value) {
          if ((mid == 0) || (a[mid - 1] < value)) return mid;
          else high = mid - 1;
        } else {
          low = mid + 1;
        }
      }
      return -1;
    }

  4. 查找最后一个小于等于给定值的元素

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    public int bsearch7(int[] a, int n, int value) {
      int low = 0;
      int high = n - 1;
      while (low <= high) {
        int mid =  low + ((high - low) >> 1);
        if (a[mid] > value) {
          high = mid - 1;
        } else {
          if ((mid == n - 1) || (a[mid + 1] > value)) return mid;
          else low = mid + 1;
        }
      }
      return -1;
    }