二分查找

前置要求：数组有序

时间复杂度：log(n)

几种常见的问题：

  1. 数组中查找target
  2. 数组中有重复，查找第一个target
  3. 数组中有重复，查找最后一个target
  4. 查找等于target或第一个小于target的值
  5. 查找等于target或第一个大于target的值

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int binarySearch(int[] a, int value) {
  int n = a.length;
  int start = 0, end = n - 1;
  //这个地方是 <=
  while (start <= end) {
    //取中间值，这个方法可能会溢出，可以采用下面的方法
    //			int mid = (start + end) / 2;
    int mid = start + (end - start) / 2;
    //更进一步，也可以使用位运算
    //			int mid = start + ((start + end) >> 1);
    if (a[mid] == value) {
      return mid;
    } else if (a[mid] > value) {
      end = mid - 1;
    } else {
      start = mid + 1;
    }
  }
  return -1;
}

再给出一个递归实现的二分查找方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int binarySearchDeep(int[] a, int value) {
  int n = a.length;
  return binarySearchDeepHelp(a, 0, n - 1, value);
}

private int binarySearchDeepHelp(int[] a, int low, int high, int value) {
  if (low > high) {
    return -1;
  }
  int mid = low + ((high - low) >> 1);
  if (a[mid] == value) {
    return mid;
  } else if (a[mid] < value) {
    return binarySearchDeepHelp(a, mid + 1, high, value);
  } else {
    return binarySearchDeepHelp(a, low, mid - 1, value);
  }
}

代码中有一个地方，我们取中间下标时，最基本的方法是mid=(low+higt)/2。但这个时候可能会造成溢出，所以我们可以采用mid=low+(high-low)。如果需要继续优化可以使用位运算mid=low+((high-low)>>1)。

局限性

  • 排序

    这个毋容置疑，不排好序，我们取中间值比较是没有意义的

  • 数组

    二分查找需要按照下标随机访问元素，数组访问的时间复杂度是o(1)，而链表是o(n)。所以二分查找不使用与链表。

  • 数据量太大时

    因为需要数组这种数据结构，而数组在内存中需要连续存储。当数据量太大，比如1gb大小，那么就需要1gb的连续内存区间，所以当数据量太大时会比较吃力。

习题

用二分查找实现，求一个数的平方根，要求精确到小数点后6位。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public double mySqrt(double x) {
  double low = 0.0, high = x;
  double mid = low + (high - low) / 2.0;
  //表示 10（^-6^）即小数点后6位
  double eps = 1e-6;
  while (Math.abs(high - low) > eps) {
    // 首先找到中间值
    mid = low + (high - low) / 2;
    double temp = mid * mid;
    // 比较并更新 high和low
    if ((temp - x) > eps) {
      high = mid;
    } else if ((temp - x) < -eps) {
      low = mid;
    } else {
      return mid;
    }
  }
  return mid;
}

变形一

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

现在有这样一个数组，[1,2,3,3,3,4,5]，要求查找3。对数组里面三个3分别命名为3a,3b,3c。按照上面二分查找方法，返回的3是3b。我们现在要求返回第一个也就是3a。

这时上面的代码就无法处理这种情况了。我们针对这个变形来实现一下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int binarySearch1(int[] a, int value) {
  int n = a.length;
  int low = 0, 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 {
      // 主要在这个地方
      //如果这个元素已经是数组的第一个元素了，那么就直接返回
      //如果不是，则判断上一个元素的值是不是等于value，如果不是则返回
      //如果是则更新high ，high=mid-1
      if ((mid == 0) || (a[mid - 1] != value)) {
        return mid;
      } else {
        high = mid - 1;
      }
    }
  }
  return -1;
}

变形二

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

在变形一种，我们查找第一个给定值的元素，我们这次查找最后一个给定值的元素。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int binarySearchLastMatch(int[] a, int value) {
  int n = a.length;
  int high = n - 1, low = 0;
  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;
}

变形三

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

给定数组，给定值，如果值存在则返回第一个元素的下标，否则返回第一个大于给定值的元素下标。

我们以这个数组为例：[1,2,4,4,5,6]。我们如果查找4，它需要返回2，即满足条件的第一个元素下标。我们如果查找3，它也需要返回2，因为3不存在数组中，第一个大于给定值的元素就是4，下标为2。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int binarySearch3(int[] a, int value) {
  int n = a.length;
  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;
}

变形四

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * 变形四，查找最后一个小于等于给定值的元素
 * [3,5,6,6,8,9,10]。
 * 当值存在时，返回最后一个等于给定值的元素
 * 不存在时，返回最后一个小于给定值的元素	
 * 查询6，7都返回下标3
 *
 * @param a     数组
 * @param value 要查找的值
 * @return
 */
public int binarySearch4(int[] a, int value) {
  int n = a.length;
  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;
}