二分查找编码套路

59 阅读 0 评论 39 点赞

我是靠谱客的博主酷炫墨镜，最近开发中收集的这篇文章主要介绍二分查找编码套路，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

二分查找的思想很好理解，但要写出没有bug的代码却并不是件容易的事。对于有序数组的二分查找，可以遵循一些套路快速写出无错代码。

下面先给出二分查找有序数组的一些问题，所有问题参考了《编程之美》。

1、给定非降序数组A，求任意一个i使得A[i]等于target，如不存在则返回-1。

2、给定非降序数组A，求最小的i使得A[i]等于target，如不存在则返回-1。

3、给定非降序数组A，求最大的i使得A[i]等于target，如不存在则返回-1。

4、给定非降序数组A，求最小的i使得A[i]大于target，如不存在则返回-1。

5、给定非降序数组A，求最大的i使得A[i]小于target，如不存在则返回-1。

6、给定非降序数组A和待插入元素target，返回待插入位置的下标。

二分查找的正确实现代码有多种形式，但要求以下几处达成一致：

1、初始化查找范围

2、计算中间位置的方法

3、循环结束条件

4、逼近方法

5、返回值

其中，

查找范围可以采用开区间，也可采用闭区间，或者半开半闭区间。

计算中间位置可以用mid=lo+(hi-lo)/2，也可以用mid=lo+(hi-lo+1)/2，在某一次探测过程中，如果数组长度为奇数，那么正中间恰好只有一个元素，此时这两种表达式效果是一样的，都取正中间元素；而如果数组长度为偶数，那么正中间没有元素，或者说有两个元素，前者取的是中间偏左的元素，后者取的是中间偏右的元素。

循环结束条件可以是lo<hi，也可以是lo<=hi，这与初始化、计算中间位置、逼近方法以及返回值都有关系。

逼近时有三种情况，分别是a[mid]<target、a[mid]>target和a[mid]==target。

下面是一种可行的组合，或者说是编码套路：

1、初始化采用闭区间，即lo=0, hi=size-1。

2、如果是求最小的i，则用mid=lo+(hi-lo)/2；如果是求最大的i，则用mid=lo+(hi-lo+1)/2；如果求任意的i，两者均可。

3、循环条件始终为lo<hi。

4、逼近时始终保持闭区间，三种情况分别处理，不做合并。写完之后如果代码可简化，再行合并处理。

5、返回值处需要对下标做有效性检查，即不能越界，另外还要检查该位置的数是否满足要求，只有两者同时成立才算成功找到。

下面根据上述编码套路，分别解决开始的6个问题，为简单说明起见，这里假定数组里存的都是整数。

1、给定非降序数组A，求任意一个i使得A[i]等于target，如不存在则返回-1。

 1 int FindPos(int a[], int size, int target) {
 2
int lo = 0, hi = size - 1, mid;
 3
while (lo < hi) {
 4
mid = lo + (hi - lo) / 2;
 5
if (target < a[mid])
 6
hi = mid - 1;
 7
else if (target > a[mid])
 8
lo = mid + 1;
 9
else
10
return mid;
11 
}
12
return (lo >= 0 && lo < size && a[lo] == target) ? lo : -1;
13 }

View Code

2、给定非降序数组A，求最小的i使得A[i]等于target，如不存在则返回-1。

 1 int FindPos(int a[], int size, int target) {
 2
int lo = 0, hi = size - 1, mid;
 3
while (lo < hi) {
 4
mid = lo + (hi - lo) / 2;
 5
if (target < a[mid])
 6
hi = mid - 1;
 7
else if (target > a[mid])
 8
lo = mid + 1;
 9
else
10
hi = mid;
11 
}
12
return (lo >= 0 && lo < size && a[lo] == target) ? lo : -1;
13 }

View Code

3、给定非降序数组A，求最大的i使得A[i]等于target，如不存在则返回-1。

 1 int FindPos(int a[], int size, int target) {
 2
int lo = 0, hi = size - 1, mid;
 3
while (lo < hi) {
 4
mid = lo + (hi - lo + 1) / 2;
 5
if (target < a[mid])
 6
hi = mid - 1;
 7
else if (target > a[mid])
 8
lo = mid + 1;
 9
else
10
lo = mid;
11 
}
12
return (lo >= 0 && lo < size && a[lo] == target) ? lo : -1;
13 }

View Code

4、给定非降序数组A，求最小的i使得A[i]大于target，如不存在则返回-1。

 1 int FindPos(int a[], int size, int target) {
 2
int lo = 0, hi = size - 1, mid;
 3
while (lo < hi) {
 4
mid = lo + (hi - lo) / 2;
 5
if (target < a[mid])
 6
hi = mid;
 7
else if (target > a[mid])
 8
lo = mid + 1;
 9
else
10
lo = mid + 1;
11 
}
12
return (lo >= 0 && lo < size && a[lo] > target) ? lo : -1;
13 }

View Code

5、给定非降序数组A，求最大的i使得A[i]小于target，如不存在则返回-1。

 1 int FindPos(int a[], int size, int target) {
 2
int lo = 0, hi = size - 1, mid;
 3
while (lo < hi) {
 4
mid = lo + (hi - lo + 1) / 2;
 5
if (target < a[mid])
 6
hi = mid - 1;
 7
else if (target > a[mid])
 8
lo = mid;
 9
else
10
hi = mid - 1;
11 
}
12
return (lo >= 0 && lo < size && a[lo] < target) ? lo : -1;
13 }

View Code

6、给定非降序数组A和待插入元素target，返回待插入位置的下标。

 1 int FindPos(int a[], int size, int target) {
 2
int lo = 0, hi = size - 1, mid;
 3
while (lo < hi) {
 4
mid = lo + (hi - lo) / 2;
 5
if (target < a[mid])
 6
hi = mid;
 7
else if (target > a[mid])
 8
lo = mid + 1;
 9
else
10
lo = mid + 1;
11 
}
12
return (lo >= 0 && lo < size && a[lo] > target) ? lo : lo + 1;
13 }