首先是二分查找，举个有序的整数数组例子（二分查找和搜索都是针对有序数组）
代码语言：javascript复制 public int rank(int key, int n) {
int lo = 0, hi = n - 1;
while (lo <= hi) {
int mid = lo ((hi - lo) >> 1); //>>1是除以2
// 为什么不直接(lo hi)>>1呢，因为lo hi可能溢出，而hi-lo不溢出，lo (hi-lo)>>1是小于hi的，也不溢出，更安全
int cmp = key - a[mid];// a为有序数组
if (cmp < 0) {
hi = mid - 1;
} else if (cmp > 0) {
lo = mid 1;
} else {
return mid;
}
}
return lo;
}如果查找到，返回数组下标mid，如果没找到，return lo；有人会问了为什么返回lo？？当然你非要在找不到的情况下返回一个负数比如-1也可以。这就是关键所在，假设a[10]={1, 2, 5, 7, 7, 12, 13, 17, 18, 20};我要查找的key是6。
第一步：lo hi mid 0 9 4 0 3 1 a[4]=7 > key=6,所以hi=mid - 1=3; lo=0 <= hi=3继续循环，mid=(lo hi)/2=1 2 3 2 cmp = 6-a[1] > 0,所以lo=mid 1=2，lo=2 <= hi=3继续循环，mid=(lo hi)/2=2 3 3 3 cmp = 6-a[2] > 0,所以lo=mid 1=3，lo=3 <= hi=3继续循环，mid=(lo hi)/2=3 3 2 cmp = 6-a[3] < 0,所以hi=mid-1=2, 此刻不满足套件，跳出，返回lo=3
返回3什么意思？你看看这个数组，是不是小于6有3个元素？
lo的值正好等于数组中小于被查找的元素的数量
那怎么知道有没有找到呢？返回的到底是命中的下标还是小于被查找元素数量呢？
用 i=rank(key, n); // 在n个元素的数组查找key=6,返回下标传给i
if （i<n&&a[i] == key）｛表示找到了｝
else ｛没找到｝
一些有序集合判断，如果集合包含这些元素，就更新数值，if（i<n&&a[i] == key）｛更新数值｝。或者要插入的位置在哪里？假如lo=5，我查找一遍，就知道他前面有5个元素，即我这次要插入的元素下标就为5（从0开始计算）
下面讲一下二分搜索
比如从有序数组中查找某个数值
lower_bound
给定长度为n的单调不下降数列a0, a1,...an-1和一个数k,求满足ai≥k条件的最小的i。不存在的情况输出n。
限制条件
代码语言：javascript复制 1≤n≤106
0≤a0≤a1≤...≤an-1<109
0≤k≤109输入
代码语言：javascript复制 n = 5
a = {2, 3, 3, 5, 6}
k = 3输出
代码语言：javascript复制 1(其中a0<3, a1>=3)这里不仅仅是二分查找了，不仅是找到下标，而是找到最小的下标
直接上代码(关键部分)
代码语言：javascript复制 int n, k;
int[] a = new int[1000001];
public void solve() {
int lo = 0, hi = n;
while (hi > lo) {
int mid = lo ((hi - lo) >> 1);
if (a[mid] >= k) {
hi = mid;
} else {
lo = mid;
}
}
System.out.println(hi);// 最后hi和lo一样，就算找不到的情况返回n，这种情况下lo=hi=n,返回哪个都一样
} 比如a[5]={2, 3, 3, 5, 6}
a[2]=3和3进行比较，可以知道解不大于2
a[1]=3和3比较，可以知道解不大于1
a[0]=2和3比较，可以知道解不小于0
所以解为1
二分搜索法是通过不断缩小解的可能存在的范围，从而求得问题最优解的方法。
