二分搜索以及其扩展形式
欢迎探讨，如有错误敬请指正
如需转载，请注明出处 http://www.cnblogs.com/nullzx/
二分搜索使用的前提是数组必须有序，在本文中，我们用lo（low）表示查找范围的起始下标，hi（hight）表示查找范围的结束下标，mid表示lo和hi的中间位置。
1. 一般情况二分搜索
现在我们来看正常的二分搜索，我们来讨论一下如果没有找到这这个元素时，lo和hi下标的元素值和key的大小关系。如果没有找到key,最后一个查找的位置一定是lo == hi的位置，下标lo之前元素的一定比key小，下标hi之后元素的一定比key大。如果当前位置（即lo和hi的下标）比key大，hi减小1；如果当前位置比key小，lo增加1。总之lo会比hi大1，结束循环。如果没有找到key，lo和hi两者之一有可能越界，hi越界时 hi为-1，lo越界时lo为a.length。在没有越界的情况下，循环结束以后，a[hi] < key，a[lo] > key。所以, 如果没有找到这这个元素，a[hi]是小于key中最接近key的值，a[lo]是大于key中最接近key的值。
2. 最小下标二分搜索
问题：如果不存在key，返回-1， 如果存在key，返回和key相等的元素中的最小的下标。
思路：如果a[mid] == key 则用lastFind记录下mid，然后在[lo, mid-1]中继续继续查找，如果在这个新范围内还能找到和key相等的元素下标，则替换lastFind，然后更新lo和hi,继续迭代上述过程，直到lo > hi；如果没有找到，lastFind就是最小下标 。
同理，最大下标二分搜索，如果a[mid] == key 则用lastFind记录下mid，然后在[mid+1，hi]中继续继续查找，……
3. 小于key的元素个数
整个数组中的元素可以分为两种，大于等于key的和小于key的。如果a[mid] >= key下一个查找的范围是[lo, mid-1]，如果a[mid] < key下一个查找的范围是[mid+1, hi], 直到lo > hi 才退出循环。最后一个查找的位置一定是lo == hi的位置，lo下标之前的一定小于key，hi下标之后的一定大于等于key。如果当前位置（即lo和hi的下标）的元素值大于等于key，hi减小1；如果当前位置小于key小，lo增加1。所以当循环结束时，lo之前下标的元素都是小于key的，而这些元素的个数等于lo。
同理，我们可以解决大于key的元素个数的问题。
4. 小于等于key的元素个数
整个数组中的元素可以分为两种，大于key的和小于等于key的。如果a[mid] > key下一个查找的范围是[lo, mid-1]，如果a[mid] <= key下一个查找的范围是[mid+1, hi]，直到lo > hi 才退出循环。最后一个查找的位置一定是lo == hi的位置，lo下标之前的一定小于等于key，hi下标之后的一定大于key。如果当前位置（即lo和hi的下标）的元素值大于key，hi减小1；如果当前位置小于等于key小，lo增加1。所以当循环结束时，lo之前下标的元素都是小于等于key的，而这些元素的个数等于lo。
同理，我们可以解决大于等于key的元素个数的问题。
5.小于等于key中下标最大
思路类似，不在赘述，但要注意lo和hi越界的情况
6.源代码
package interview_question;
public class BinarySearch {
/*普通二分搜索，如果找到key，返回任意一个和key相等的元素下标，否则返回-1*/
public static int find(int[] a, int key){
int lo = 0, hi = a.length - 1;
while(lo <= hi){
int mid = (lo + hi) / 2;
if(a[mid] > key){
hi = mid - 1;
}else if(a[mid] < key){
lo = mid + 1;
}else{
return mid;
}
}
return -1;
}
/*
如果不存在目标元素，返回-1， 如果存在目标元素，返回和目标元素相等中下标最小的
*/
public static int findWithMinIndex(int[] a, int key){
int lo = 0, hi = a.length - 1;
int lastFind = -1;
while(lo <= hi){
int mid = (lo + hi)/2;
if(a[mid] > key){
hi = mid - 1;
}else if(a[mid] < key){
lo = mid + 1;
}else{
lastFind = mid;
hi = mid - 1;
}
}
return lastFind;
}
/*上述问题的第二种实现方法
public static int findWithMinIndex(int[] a, int target){
int lo = 0, hi = a.length - 1;
while(lo <= hi){
int mid = (lo + hi)/2;
if(a[mid] >= target){
hi = mid - 1;
}else{
lo = mid + 1;
}
}
if(lo < a.length && a[lo] == target){
return lo;
}else{
return -1;
}
}
*/
/*返回数组元素 <key 的元素个数*/
public static int findLessCnt(int[] a, int key){
int lo = 0, hi = a.length - 1;
while(lo <= hi){
int mid = (lo + hi)/2;
if(a[mid] >= key){
hi = mid - 1;
}else{
lo = mid + 1;
}
}
return lo;
}
/*返回 数组元素中 <=key 的元素个数*/
public static int findLessEqualCnt(int[] a, int key){
int lo = 0, hi = a.length - 1;
while(lo <= hi){
int mid = (lo + hi) / 2;
if(a[mid] > key){
hi = mid - 1;
}else{
lo = mid + 1;
}
}
return lo;
}
/*如果未找到key，返回元素值比目标小且最接近目标元素的下标*/
public static int findLessEqual(int[] a, int key){
int lo = 0, hi = a.length-1;
/*排除lo和hi越界的情况*/
if(a[lo] >= key){
return lo;
}
if(a[hi] <= key){
return hi;
}
while(lo <= hi){
int mid = (lo + hi)/2;
if(a[mid] >= key){
hi = mid - 1;
}else if(a[mid] < key){
lo = mid + 1;
}
}
return a[lo] == key ? lo : hi;
}
}