【原创】编程之美之二分搜索

二分搜索思想

给定一个有序（不降序）数组a， 求任意一个i使得a[i]等于v，不存在返回-1。

二分搜索的思路是：选一个数组中间值m，将有序数组一分为二。如果a[m]==v，搜索结束；如果a[m]>v，搜索[left, m)，反之搜索(m, right]。如图所示。

那么如果数组中没有v时，何时终止搜索呢？一个显而易见的条件是数组不能再进行划分搜索时，即left > right 。

二分搜索可以有以下变种：

1. 给定一个有序（不降序）数组a， 求最大的i使得a[i]等于v，不存在返回-1

2. 给定一个有序（不降序）数组a， 求最小的i使得a[i]等于v，不存在返回-1

3. 给定一个有序（不降序）数组a， 求最大的i使得a[i]小于v，不存在返回-1

4. 给定一个有序（不降序）数组a， 求最小的i使得a[i]大于v，不存在返回-1

变种的解法也简单，对变种1来说，当找到a[m] == v时，为了接着找到更大的（最右边的）元素，需要搜索[m, right]。看到差别了吧，之所以把m包进来，就是防止m右边再没有等于v的元素。

变种3，当a[m] < v时，搜索[m, right]以找到比m更右边的元素。当a[m] >= v时，搜索[left, m)。终止条件

这里说一下写代码时的思考——比如，为什么循环控制要用left < right -1 而不是 left < right 等。

实现分析

思路很简单，关键是循环控制。

先看一下中间值是怎么选的：mid = left + (right - left)/2 。 这个公式有个特点，当left==right或left==right -1 时，mid==left。什么意思呢？如图所示，(a)的下一次划分可能还是(a)， (b)的下一次划分还是(b)，这导致我们的循环不会停了。。。因为left永远不会大于right了。。。

所以，为了让结束搜索，我们可以限制left、right最少夹三个元素。即当一下条件出现时，搜索终止。

记得搜索终止后，别忘了判断a[left]、a[right]是否符合条件。

代码

下面是java版本的变种3实现（变种1《编程之美》里已有代码）：

1 void checkValid(int[] a, int l, int r) {
 2         if (a == null || l < 0 || r < 0 || l > r)
 3             throw new IllegalArgumentException();
 4 }
 5 int bsMaxIndexLessThanV(int[] a, int left, int right, int v) {
 6 
 7             checkValid(a, left, right);
 8 
 9             int m, l = left, r = right;
10             while(l < r-1){
11                 m = l + (r - l)/2;
12                 
13                 if( a[m] < v)
14                     l = m;
15                 else
16                     r = m - 1;
17                     
18             }
19             
20             if(v > a[r])
21                 return r ;
22             if(v > a[l])
23                 return l;
24             return -1;
25 }      

 测试用例

1. 检查输入是否正确

2. 分别用包含一个元素，两个元素，多个元素的数组测试。保证corner case：

1     @Test
 2     public void testBsMaxLess() {
 3         int[] a1 = { 1 };
 4         Assert.assertEquals(-1, bsMaxIndexLessThanV(a1, 0, 0, 1));
 5         Assert.assertEquals(0, bsMaxIndexLessThanV(a1, 0, 0, 2));
 6         
 7 
 8         int[] a2 = { 1, 2 };
 9         Assert.assertEquals(-1, bsMaxIndexLessThanV(a2, 0, 1, 1));
10         Assert.assertEquals(0, bsMaxIndexLessThanV(a2, 0, 1, 2));
11         Assert.assertEquals(1, bsMaxIndexLessThanV(a2, 0, 1, 3));
12         
13         int[] a3 = new int[] { 2, 3, 3, 3, 3, 3, 3, 3, 4 };
14         Assert.assertEquals(-1, bsMaxIndexLessThanV(a3, 0, a3.length - 1, 2));
15         Assert.assertEquals(8, bsMaxIndexLessThanV(a3, 0, a3.length - 1, 10));
16         Assert.assertEquals(0, bsMaxIndexLessThanV(a3, 0, a3.length - 1, 3));
17         Assert.assertEquals(7, bsMaxIndexLessThanV(a3, 0, a3.length - 1, 4));
18     }      

Test case

转载于:https://www.cnblogs.com/lina/p/3183886.html