二分查找详解
二分查找详解<div id="cnblogs_post_body">很多书上都会讲到二分查找（数据结构与算法教材、《编程之美》、《编程珠玑》），这也是一个经典的面试题。尽管它很常见，大家也很熟悉，但是却不一定能够完美地写出来。今天自己整理了一下，把三种二分查找算法（找最后一次出现的某值v，找第一次出现的某值v和普通的二分查找）进行了梳理。
问题描述：有一个按非降序排列的有序数组a和一个数v
1. 求数组a中最后一次出现的数v的下标
设l为左边界，h为右边界，mid = (l+h)/2，那么，根据mid的取值，分三种情况:
(1) a < v，说明v如果在数组中，应该出现在mid右侧，则调整左边界，l = mid + 1
(2) a > v，说明v如果在数组中，应该出现在mid左侧，则调整右边界，h = mid - 1
(3) a == v，中间值等于v，而要求的是最后一次出现的v。最后出现的v值一定在mid的右边或者就是mid位置的这个值，所以我们应该调整左边界，l = mid。
以上三步是循环体中的关键步骤，但容易出错的地方不在这三步中，而在于循环结束的条件。
为了更清楚地说明问题，下面讨论一下当循环体内l和h之间（包含l和h）最后只剩3个和2个元素时的情况，初始元素个数超过3个的最后都会转化为这两种情况之一。
只剩3个元素时，可能出现2中情况，一种是其中里面含有v，另一种是不含v。假设v = 2，那么含有v的可能出现以下几种情况:
(1) 若v只出现一次，可能出现的最终状态将如下图所示：
初始状态：http://pic002.cnblogs.com/images/2012/431941/2012072719103872.png最终状态http://pic002.cnblogs.com/images/2012/431941/2012072719111114.png，l = h
初始状态：http://pic002.cnblogs.com/images/2012/431941/2012072719113151.png 最终状态http://pic002.cnblogs.com/images/2012/431941/2012072719114319.png这种情况需要特别注意，因为此时l = mid, h = l + 1, 如果继续循环，l和h的值将不会改变
初始状态：http://pic002.cnblogs.com/images/2012/431941/2012072719121273.png最终状态http://pic002.cnblogs.com/images/2012/431941/2012072719122498.png，l = h
(2)若v出现两次，可能出现的最终状态如下：
初始状态：http://pic002.cnblogs.com/images/2012/431941/2012072719125640.png最终状态http://pic002.cnblogs.com/images/2012/431941/2012072719130551.png， h = l + 1
初始状态：http://pic002.cnblogs.com/images/2012/431941/2012072719132934.png 最终状态http://pic002.cnblogs.com/images/2012/431941/2012072719134185.png，h = l + 1，这种情况也很特殊，因为此时l和h位置的值都是v
(3)若v出现三次，可能出现的最终状态如下：
初始状态：http://pic002.cnblogs.com/images/2012/431941/2012072719140883.png 最终状态http://pic002.cnblogs.com/images/2012/431941/2012072719142533.png ，h = l + 1，此时l和h位置的值也都是v
如果数组中不含v，那么可能会出现以下两种情况：
(1) 中间元素小于v
初始状态：http://pic002.cnblogs.com/images/2012/431941/2012072719145170.png最终状态 http://pic002.cnblogs.com/images/2012/431941/2012072719150242.png ， l = h
(2) 中间元素大于v
初始状态：http://pic002.cnblogs.com/images/2012/431941/2012072719153343.png 最终状态 http://pic002.cnblogs.com/images/2012/431941/2012072719154580.png, l = h
若数组中只剩两个元素，那么这两个元素中可能含v，也可能不含v。如果含有v，有两种情况：
(1) a = v
初始状态：http://pic002.cnblogs.com/images/2012/431941/2012072719161681.png最终状态http://pic002.cnblogs.com/images/2012/431941/2012072719162626.png， h = l + 1
(2) a != v
初始状态：http://pic002.cnblogs.com/images/2012/431941/2012072719165328.png 最终状态http://pic002.cnblogs.com/images/2012/431941/2012072719170484.png， l = h
如果两个元素中不含v，也有两种情况：
(1) a < v
初始状态： http://pic002.cnblogs.com/images/2012/431941/2012072719191271.png 最终状态http://pic002.cnblogs.com/images/2012/431941/2012072719192212.png， l = h
(2) a > v
初始状态：http://pic002.cnblogs.com/images/2012/431941/2012072719194861.png 最终状态 http://pic002.cnblogs.com/images/2012/431941/2012072719200281.png h = l - 1
从上面的分析可以得出结论，循环结束的条件应该是 l + 1 < h，结束以后，需要检查l + 1位置的值是否和v相等，相等，则l + 1是所求的位置，否则，检查l位置的值是否和v相等，若相等，则l是所求的位置，否则，说明原数组中不存在v，返回-1
代码如下：
<div class="cnblogs_code">/*在一个数组里面查找最后一次出现的值v*/int binarySearchLast(int *a, int l, int h, int v){ if(!a || l > h) return -1; int mid; while (l+1 < h) { mid = (l+h)/2; if(a < v) l = mid + 1; else if(a == v) l = mid; else h = mid - 1; } if(a1] == v) return l+1; else if(a == v) return l; else return -1;}
页:
[1]