這個東西研究了好長時間，做下記錄。
二分查找的整體結(jié)構(gòu)如下：

while(lo ? hi){
  mid = (lo + hi)/2;
  if(key ? arr[mid])
     //......
  else
    //...... 
}

這片文章總結(jié)的挺好的，但是我又在解決其他問題的時候遇到不一樣的套路，比如這個。主要糾結(jié)就在于第一個問號。
經(jīng)過實驗發(fā)現(xiàn)，一般我們的搜索都是在完全閉區(qū)間中進行搜索的，在這種情況下，第一個問號那里，必須寫<=。但如果寫成lo < hi - 1這種形式，意味著這是半開區(qū)間，在這個循環(huán)中不會找到hi這個右邊界。而在之前的那種情況下是可以找到右邊界的。代碼如下：

情況1：lo <= hi后面的lo和hi必須要mid加一或者減一的，返回的索引是mid。完整閉區(qū)間。
情況2：lo < hi-1后面的lo和hi必須等于mid，并且返回的索引是lo。去掉了右邊界。

情況1的常規(guī)代碼：

while(lo <= hi){
  mid = (lo + hi)/2;
  if(x < arr[mid]) hi = mid -1 ;
  else if(x > arr[mid]) lo = mid + 1;
  else return true;
}
return false;

情況2的常規(guī)代碼：

while(lo < hi-1){
  mid = (lo + hi)/2;
  if(x < arr[mid]) hi = mid;
  else lo = mid;
}
return arr[lo] == x;

在這個基礎(chǔ)上，我還想了如果寫了lo < hi這個條件，會出現(xiàn)什么情況。其實這個，經(jīng)過實驗，也是完全可以查找的，并且是完全閉區(qū)間的，但是需要多填一句代碼。因為前面第一種情況已經(jīng)實現(xiàn)了，所以沒有必要研究這個，盡管使用上面的兩種代碼。

二分查找，看似簡單，但還是很難寫對。