二分查找有幾種寫法？它們的區別是什麼？

比如說while(l&或者是while(l&<=r) if(...) l=mid; r=mid;

這些到底是怎麼區分的呢？一直搞不清楚，希望大神指教！

---

64種。理由如下：

對其進行分類：

取整方式：向下取整 向上取整 （共2種）

區間開閉：閉區間 左閉右開區間 左開右閉區間 開區間 （共4種）

問題類型：

對於不下降序列a，求最小的i，使得a[i] = key

對於不下降序列a，求最大的i，使得a[i] = key

對於不下降序列a，求最小的i，使得a[i] &> key

對於不下降序列a，求最大的i，使得a[i] &< key

對於不上升序列a，求最小的i，使得a[i] = key

對於不上升序列a，求最大的i，使得a[i] = key

對於不上升序列a，求最小的i，使得a[i] &< key

對於不上升序列a，求最大的i，使得a[i] &> key

（共8種）

綜上所述，二分查找共有 種寫法。

演算法的目的是解決問題，下面以針對不下降序列a的4個問題為例，給出我認為效率較高，較為簡潔的代碼。

對於不下降序列a，n為序列a元素的個數，key為關鍵字：

1.求最小的i，使得a[i] = key，若不存在，則返回-1

int binary_search_1(int a[], int n, int key)
{
int m, l = 0, r = n - 1;//閉區間[0, n - 1]
while (l &< r) { m = l + ((r - l) &>&> 1);//向下取整
if (a[m] &< key) l = m + 1; else r = m; } if (a[r] == key) return r; return -1; }

2.求最大的i，使得a[i] = key，若不存在，則返回-1

int binary_search_2(int a[], int n, int key)
{
int m, l = 0, r = n - 1;//閉區間[0, n - 1]
while (l &< r) { m = l + ((r + 1 - l) &>&> 1);//向上取整
if (a[m] &<= key) l = m; else r = m - 1; } if (a[l] == key) return l; return -1; }

3.求最小的i，使得a[i] &> key，若不存在，則返回-1

int binary_search_3(int a[], int n, int key)
{
int m, l = 0, r = n - 1;//閉區間[0, n - 1]
while (l &< r) { m = l + ((r - l) &>&> 1);//向下取整
if (a[m] &<= key) l = m + 1; else r = m; } if (a[r] &> key) return r;
return -1;
}


4.求最大的i，使得a[i] &< key，若不存在，則返回-1

int binary_search_4(int a[], int n, int key)
{
int m, l = 0, r = n - 1;//閉區間[0, n - 1]
while (l &< r) { m = l + ((r + 1 - l) &>&> 1);//向上取整
if (a[m] &< key) l = m; else r = m - 1; } if (a[l] &< key) return l; return -1; }

實際上，對於3、4，也可以先判斷解是否存在，再進行二分查找。

顯然，上面的代碼還不夠簡潔。下面給出我認為最簡潔的代碼：

1.

int ans = std::lower_bound(a, a + n, key) - a;
ans = (ans == n || a[ans] != key) ? -1 : ans;


2.

int ans = std::upper_bound(a, a + n, key) - a;
ans = (ans == 0 || a[ans - 1] != key) ? -1 : ans - 1;


3.

int ans = std::upper_bound(a, a + n, key) - a;
ans = (ans == n) ? -1 : ans;


4.

int ans = std::lower_bound(a, a + n, key) - a;
ans = (ans == 0) ? -1 : ans - 1;


（逃

---

如果是double，完全沒什麼難度，重點坑就是整數的。。。表示被坑過好多遍，畢竟弱渣。。。

首先，如果題目屬於"二分值越大越符合條件"，即要求符合條件的最小值，那就是

while(r&>l){mid=(l+r)/2。。。}

然後更新是不符合條件l=mid+1，否則是r=mid

反之，即 題目屬於"二分值越小越符合條件"，即要求符合條件的最大值，那就是

while(r&>l){mid=(l+r+1)/2。。。}

然後更新是符合條件l=mid，否則是r=mid-1

至於為啥？→_→其實只要試試r-l=1的例子。。。感覺就理解了

upd:又想起一坑{其實是看到有人寫了}，如果涉及負數，最好用mid=l+(r-l)/2代替第1類，mid=l+(r-l+1)/2代替第2類

---

有多少種寫法都不重要，

重要的是要會寫一種對的。

首先有幾個數字要注意

中位數有兩個，

1. 下位中位數：lowerMedian = (length - 2) / 2
2. 上位中位數：upperMedian = length / 2

常用的是下位中位數，通用的寫法如下，語言int經常自動向下取整，

median = (length - 1) / 2

指針的區間當然可以開區間，也可以閉區間，也可以半開半閉。但老老實實兩頭取閉區間總是不會錯。上面的中位數，轉換成兩頭閉區間 [low,high] 就變成下面這樣：

median = low + (high - low) / 2

這裡還有個常見的坑，不要圖快用加法，會溢出，

median = ( low + high ) / 2 // OVERFLOW

另外一個關鍵點是「終結條件」。

不要以 low == high 做終結條件。會被跳過的，

if (low == high) {
return (nums[low] &>= target)? low : ++low;
}


不相信在 [1, 5] 里找 0 試試？

正確的終結條件是：

low &> high

也就是搜索空間為空。

滿足終結條件以後，返回值完全不需要糾結，直接返回低位 low。

因為回過頭去放慢鏡頭，二分查找的過程就是一個 維護 low 的過程：

low從0起始。只在中位數遇到確定小於目標數時才前進，並且永不後退。low一直在朝著第一個目標數的位置在逼近。知道最終到達。

至於高位 high，就放心大膽地縮小目標數組的空間吧。

所以最後的代碼非常簡單，

public int binarySearch(int[] nums, int target) {
int low = 0, high = nums.length-1;
while (low &<= high) { int mid = low + (high - low) / 2; if (nums[mid] &< target) { low = mid + 1; } if (nums[mid] &> target) { high = mid - 1; }
if (nums[mid] == target) { return mid; }
}
return low;
}


遞歸版也一樣簡單，

public int binarySearchRecur(int[] nums, int target, int low, int high) {
if (low &> high) { return low; } //base case
int mid = low + (high - low) / 2;
if (nums[mid] &> target) {
return binarySearchRecur(nums,target,low,mid-1);
} else if (nums[mid] &< target) { return binarySearchRecur(nums,target,mid+1,high); } else { return mid; } }

但上面的代碼能正常工作，有一個前提條件：

元素空間沒有重複值

推廣到有重複元素的空間，二分查找問題就變成：

尋找元素第一次出現的位置。

也可以變相理解成另一個問題，對應C++的 lower_bound() 函數

尋找第一個大於等於目標值的元素位置。

但只要掌握了上面說的二分查找的心法，代碼反而更簡單，

public int firstOccurrence(int[] nums, int target) {
int low = 0, high = nums.length-1;
while (low &<= high) { int mid = low + (high - low) / 2; if (nums[mid] &< target) { low = mid + 1; } if (nums[mid] &>= target) { high = mid - 1; }
}
return low;
}


翻譯成遞歸版也是一樣，

public int firstOccurrenceRecur(int[] nums, int target, int low, int high) {
if (low &> high) { return low; }
int mid = low + (high - low) / 2;
if (nums[mid] &< target) { return firstOccurrenceRecur(nums,target,mid + 1,high); } else { return firstOccurrenceRecur(nums,target,low,mid-1); } }

以上代碼均通過leetcode測試。標準銀彈。每天早起寫一遍，鍛煉肌肉。

最後想說，不要怕二分查找難寫，邊界情況複雜。實際情況是，你覺得煩躁，大牛也曾經因為這些煩躁過。一些臭名昭著的問題下面，經常是各種大牛的評論（噁心，變態，F***，等等）。而且這並不考驗什麼邏輯能力，只是仔細的推演罷了。拿個筆出來寫一寫，算一算不丟人。很多問題徹底搞清楚以後，經常就是豁然開朗，然後以後妥妥舉一反三。以上。

---

據說十個二分九個錯…

個人認為可能遇到的問題在於：數列中相同值的處理；循環不變式的終止條件；邊界條件的判定。

條件為升序排列A，函數會返回第一個&>=key的index，以下幾種寫法是等價的。不妨體會下之間細微的差別。

1.

int lower_bound(int A[], int n, int key) {
if (A[n - 1] &< key) return n; int lo = 0, hi = n - 1; while (lo &< hi) { int mid = (lo + hi) / 2; if (A[mid] &< key) lo = mid + 1; else hi = mid; } return lo; }

2.

int lower_bound(int A[], int n, int key) {
if (A[0] &>= key) return 0;
int lo = 0, hi = n - 1;
while (lo &< hi) { int mid = (lo + hi + 1) / 2; if (A[mid] &>= key) hi = mid - 1; else lo = mid;
}
return lo + 1;
}


3.

int lower_bound(int A[], int n, int key) {
if (A[0] &>= key) return 0;
int lo = 0;
for (int p = n - 1; p &> 0; p /= 2) {
if (lo + p &< n A[lo + p] &< key) lo += p; } return lo + 1; }

4.

int lower_bound(int A[], int n, int key) {
if (A[n - 1] &< key) return n; int hi = n - 1; for (int p = n - 1; p &> 0; p /= 2) {
if (hi - p &>= 0 A[hi - p] &>= key) hi -= p;
}
return hi;
}


簡言之，1、4的方式可以找到區間左端點，2、3的方式可以找到區間右端點。

---

首先mid=(l+r)/2和mid=(l+r+1)/2也會有不同。

然後只要代入l=0,r=2或者l=0,r=3試一下你就懂了。

---

二分搜索法簡單分析與總結

---

題主舉的是開閉區間的表示的區別，這兩者的選擇，我的看法是看你習慣了

說到面試，其實這題的難點在於最後邊界條件，那麼我們根本不用判斷那個邊界，二分到區間小到一定程度，比如5個元素以下，就順序查找好了，反正也是O(lgN)的，而且最後5個元素順序查找平均也只需要比較兩三次而已，跟你二分差不多，我本人也很推薦在實際工程中這樣寫，可以規避很多麻煩的bug，用最穩妥的辦法解決問題

---

總的來說，二分主要是兩種情況，一種是浮點數二分，一種是整數二分，框架不同。

浮點數二分，eps往往指的是要求達到的精度，judge()是判斷是否符合條件的函數，符合返回true，求最小的符合條件的解：

#define eps 1e-8

double search(double low, double high) {
while (high - low &> eps) {
double mid = (low + high) / 2;
if (judge(mid)) high = mid;
else low = mid;
}
return (low + high) / 2;
}


整數二分寫法會有很多種，在acm比賽時，經常使用到的是同一種形式，此種寫法理解後很容易記憶，變通性也很高。

整數二分，都是閉區間，ans返回找到的第一個滿足條件的解（如找到一個有序數組中第一個大於或者等於某一個數值的數在數組中的位置），找不到解時返回-1

int search(int low, int high) {
int ans = -1;
while (low &<= high) { int mid = low + (high - low) / 2; if (judge(mid)) { ans = mid; high = mid - 1; } else low = mid + 1; } return ans; }

---

來說兩個吧，只要掌握這兩個就行了，包你不遇坑。

既然二分搜索，肯定是要用到區間，那麼就先規定區間用半閉半開區間，例如左閉右開區間，[lb, m), [m, ub)。

那麼第一種寫法：

while(ub-lb&>1) { // [lb, lb+1) == lb
int mid = (ub+lb) &>&> 1;
if(C(mid)) ub = mid; // 看情況
else lb = mid;
}


第二種寫法，針對精度：

for(int i=0; i&<=10000; ++i) { double mid = (ub + lb) / 2.0; if(C(mid)) ub = mid; else lb = mid; }

---

直覺考慮，統一以（l == r)為終止條件，若要求結果盡量大（如符合條件的最大值）mid =(l+r)/2+1（mid大一點）;若要求盡量小mid = (l+r)/2.（mid小一點）。

然後再根據前邊mid的不同寫出對l和r的迭代就行了。注意最後l和r的取值永遠在[(l+r)/2，(l+r)/2+1]之中。

---

我一直帶等號，然後左加一右減一

---

主要是區間的開閉不一樣吧

我通常寫的是：

while(l &< r - 1)

if(…) l = mid

else r = mid

這樣表示當前區間是[l,r)，最後l就是答案

當然也有人這麼寫的：

while(l &< r)

if(…)l = (mid - 1),ans = l

else r = (mid + 1),ans = r

這樣表示當前區間是[l,r]，最後答案是ans

while中的條件怎麼寫？

很簡單，while中的條件就是當前區間還剩不止一個元素的情況（或者說，還剩少於一個元素的情況的相反的條件）。

比如，我取左閉右開區間，噹噹前區間是[l,l+1)的時候就只剩一個元素l了，如果(r &<= l + 1)滿足就說明還剩不到一個元素，因此我的條件就是not (r &<= l + 1),即l &怎麼確定最後的答案？

事實上，你要知道你的演算法最後l和r會停留在什麼什麼位置，比如在上面說的第一種寫法中，最後會在區間為[l,l + 1)時停下，此時就只剩l一個元素了，因此l就是答案。

搞不清楚的話可以像第二種寫法那樣用一個ans來保存最後的答案...

---

其實就是區間開閉不一樣，常見錯誤就是while(l&

哈哈，Programming Perl上說二分查找10個人有9個人寫不對。

我當時拿去問同學，還真是這樣，所以為了準備面試我就去背了一下，其實只要注意幾個關鍵點就好了，一個是循環中止條件，還有就是left和right的變化。

我嘗試了很多就這一個版本是對的……至於有沒有其它的版本我並不知道。

或許有？

// find x in arr[0...n-1]
int bsearch(int arr[], int size, int x) {
int left = 0,
right =size-1,
mid = 0;
while (left &<= right) { //注意是&<= mid = (right - left)/2 + left; // 防止溢出 if (arr[mid] == x) return mid; else if (arr[mid] &< x) left = mid + 1; else right = mid - 1; } return -1; }

---

當年學的時候和題主有同樣的迷茫。以至於出現了區間內元素小於三個就 break 出來暴力判斷的醜陋 hack。後來無意中看了一次算導的前幾章，知道了有個叫 循環不變式 的東西，自行腦補之後感覺豁然開朗。

建議題主先去看一下算導里的這一部分，看看它是怎麼用循環不變式解釋插入排序的。

下面我用一個在遞增序列中查找 x 的例子試著解釋一下把：

int l = 0,r = n-1; // x 必然存在於區間 [0,n-1] 內。(這裡使用閉區間表示)
while( r-l+1 &> 1 ) // 只要區間的長度大於1，就繼續細分這個區間
{
// 循環不變式 : x 在區間 [l,r] 內。
int m = (l+r+1)/2; // 這裡涉及到應該上取整還是下取整的問題
if( x &< v[m] ) r = m-1; // x 在區間 [l,m-1] 內 else l = m; // x 在區間 [r,m] 內 }

這個循環能夠結束的條件是，區間內只剩下一個元素。

並且按照我們的預期 [l,r] 這個區間在每次循環後都應該變小。

[l,r] 在每次循環後根據不同情況有可能變成 [m,r] 或 [l,m-1]。

當區間長度大於2時，m 無論時上下取整，都會使區間縮小，這時上下取整都時可以的。

然而當區間長度恰好為 2 時，若採用下取整，m 恰好會等於 l，若此時恰好 x &>= v[m]，那麼區間變為 [m,r] 就沒有被縮小，而是和循環開始時一樣，自此陷入無盡的重複。而採用上取整，m 會恰好等於 r，此時無論變為 [m,r] 還是 [l,m-1] 都使得區間縮小了，循環能順利跳出。

至於寫法幾種的問題：

1. 開區間或閉區間：只是區間如何表示的問題，兩者本質是一樣的，都不過是在表達 「x 在這個區間內」。僅僅影響到 判斷區間是否只剩一個元素 的寫法。

2. 上取整或下取整：當區間長度為 2 時若取整處理不當可能造成死循環，根具情況分析一下，選擇一種。
3. lower_bound 或 upper_bound：一個是找滿足條件的最前面的數，一個是找滿足條件的最後面的數。看起來似乎是不同的寫法，實質上這兩個都是在找某一個數，前者是找 第一個滿足條件的數，而後者時在找 最後一個滿足條件的數。相應的循環不變式就變成了 "第一個滿足條件的數 在區間 [l,r] 內"。因此這兩個實際只不過是在找兩個不一樣的值。算不上兩種寫法。

---

不管怎麼寫，只要遵循一個原則，就是L是符合條件的的，R是不符合的（反過來也一樣）。這個不變數將貫穿整個二分的過程。

什麼意思呢？舉個栗子，你需要在[l,r]區間中找到符合條件的最大的x，按照上面的原則，你的初始條件就應該是L=l, R=r+1, 注意這裡的R是不符合條件的，因為它超出了邊界，所以它不可能是答案。這時候，你的mid如果合法，就說明答案大於等於mid，所以應該更新L，如果mid不合法，直接把R設成mid。至於如何判斷合法（是大於等於還是大於），該不該加一減一，按照這個原則都可以很容易想出來。

這樣在整個二分的過程中，你會發現，R在任何時候都不可能是答案，那麼這個循環的停止條件也很容易判斷了，就是L+1=R，這時候說明L已經是符合條件的最大值了，因為再加一就是非法值。

---

一百個讀著有一百個哈姆雷特

一百個碼農有一百種二分寫法

---

給樓主推薦一篇超棒的文章：漫談二分查找-Binary Search

---

Mid=min+(max-min)/2

,可以有效防止各種溢出。

---

今天學一個新演算法的時候, 突然發現我以前的二分一直有點問題, 雖然以前的寫的二分都能AC, 但還是有些問題, 如果題目給出的區間內沒有解, 我的二分可能就會出問題. 加上更久之前發現自己三分寫法的問題, 感覺自己能有些題目能AC真是運氣好, 所以乾脆把所有二分三分思路整理一下.

---

整數二分

二分的坑點主要在整數的二分, 如果沒有寫好會出現死循環的問題.

二分的原理是利用區間內值有序的特點, 不斷讓可行區間減半, 最終可行區間長度減到1得到答案

要保證二分能得到正確答案並且不會死循環, 要保證兩個條件:

1. 解一直在可行區間里

2. 每次判斷後可行區間都會縮小(特別是左右端點相距為1的時候)

第一點很好保證, 第二點在可行區間長度大於2的時候不會出問題.

但是當可行區間左右端點相距為1的時候, 因為是整數, 所以中間值mid只能只能取得左端點或者右端點. 這時如果沒有處理好, 就可能會陷入死循環.

所以重點要考慮的是當左右端點相距為1的時候, 執行判斷後, 可行區間是否會縮小.

我們寫二分的時候, 可以先保證第一點, 讓解一直在可行區間裡面, 然後再根據左右端點相距1的時候的情況, 調整mid到底是向上還是向上取整, 是+1還是-1

下面我們看幾個常見的二分寫法

---

二分搜索

寫法一

在遞增數組中尋找等於key值的位置

最初可行區間為[l, r)

循環退出條件為:

1. 找到了key, 直接return返回

2. 可行區間長度變為0, 無解, 退出並循環返回-1

int bsearch(int *a, int l, int r, int key)
{
int mid;
while(l&

1. 當a[mid]偏小, 可行區間由[l, r)變為[mid+1, r), 因為數組遞增, a[mid]&< key, 所以解一定還在[mid+1, r)中
2. 當a[mid]偏大, 由[l, r)變成[l, mid), 沒問題

再來考慮當l=r-1時

1. 如果a[mid]偏小, 因為l=mid+1, 所以區間縮小了, 沒問題;

2. a[mid]偏大, r = mid, 此時mid=l, 所以r也左移了, 區間縮小沒問題

而mid = l + (r-l);之所以寫成這樣而不是mid = (l+r)/2;是為了防止溢出, 並且具有更好的通用性(如果l和r是迭代器或者指針, 第一種就不行了, 因為迭代器或指針是不能相加的)

寫法二

在遞增數組中尋找等於key值的位置

最初可行區間為[l, r]

循環退出條件為:

1. 找到了key, 直接return返回

2. 可行區間長度變為0, 無解, 退出並循環返回-1

int bsearch(int *a, int l, int r, int key)
{
int mid;
while (l &<= r) { mid = l + (r - l) / 2; if (a[mid] &< key) l = mid + 1; else if (a[mid] == key) return mid; else r = mid - 1; } return -1; }

1. 分析同上, 偏小[l, r]-&>[mid+1, r], 偏大[l, r]-&>[l, mid-1], 判斷之後區間縮小並且解還在區間內
2. 但左右端點距離為1時, 如果偏小l=mid+1, 左端點右移, 區間縮小; 偏大r=mid-1, 右端點左移, 區間縮小;

---

二分求下界

區間[l, r)中, [l, x)都不滿足某條件, [x, r)都滿足條件, 求x

例如: 遞增數列求第一個大於等於key的值([l, x)都滿足&< key, [x, r)都滿足&>=key, 求x)

寫法一

遞增數組求第一個大於等於key的值, 如果不存在, 返回最初區間的最後一個位置+1(r+1)

最初可行區間: [l, r]

退出循環條件, 可行區間長度變成1

int lowerBound(int *a, int l, int r, int key)
{
int mid;
while(l &< r) { mid = l+(r-l)/2; if(a[mid] &< key) l = mid+1; else r = mid; } if(a[l] == key) return l; else return l+1; }

a[mid]&< key, [l, r] -&> [mid+1, r], 解還在區間內

a[mid]&>=key, [mid, r], 因為可能等於key, 所以要保留mdi, 解還在區間內

當l=r-1時, mid=l, 如果a[mid] &< key, l = mid+1, 左端點右移, 區間縮小;

如果a[mid]&>=key, r = mid = l, 右端點左移, 區間縮小

最後還有一個判斷, 是因為當解在最後一個位置時, 最後的區間變成了[r, r], 當無解的時候, 最後的區間也是[r, r], 所以要就一個判斷看有沒有解.

寫法二

//同上, 最初可行區間為[l, r]
int lowerBound(int *a, int l, int r, int key)
{
int mid;
while(l&<=r) { mid = l + (r-l)/2; if(a[mid] &< key) l = mid+1; else r = mid-1; } return l; }

和上一個大同小異, 但這個最後不用在判斷是否存在, 因為再區間長度變成1的時候, 即l==r時, 還會在循環一次, 如果mid(mid= l)滿足, l不變,如果mid不滿足, l=mid+1. 相當於上一個程序循環外的判斷放到了循環裡面

---

浮點數二分

相比於整數的二分, 浮點數的二分好寫多了, 因為沒有取整的問題

有兩種寫法

1. 以循環次數為循環終止條件

2. 以精度位循環終止條件

for(int i=0; i&<60; ++i) //i為循環次數, 60次循環可以讓精度達到初始區間長度的1/1e18 { mid = (l+r)/2; ... } while(r-l&

第二種如果eps太小, 由於浮點數的精度問題, 還是可能會陷入死循環, 所以推薦第一種

三分

三分可以用來求有極值點並且極值點兩邊一邊遞增一邊遞減的函數的極值點

同樣有整數三分和浮點數三分

整數三分

//凸函數求極值點
int lm, rm;
while(l& a[rm]) r = rm;
else if(a[lm] == a[rm]) r=rm, l=lm;
else l = lm;
}


特別注意, 當這個函數可能是單調函數時(極值點在端點), 三分演算法無法到達端點位置, 所以要特判一下兩個端點, 以前做題的時候被坑過

浮點數三分和二分一樣可以用循環次數或精度來控制循環終止

---

推薦閱讀：