第一周——二分查找（主要教會你如何使用二分查找的模版）

• 二分法的基本思想：
• 適用二分法題目所具有的特點：
• 二分法的兩種模版是針對于下面這兩種情況的：
• • 模版一：當要二分的答案在綠色的區間段的時候：
  • 模版二：當要二分的答案在紅色的區間段的時候：
  • 為什么模版二在計算mid的時候多加了1？
  • 總結：

二分法的基本思想：

二分法的思想是非常簡單的，但是存在著一定的問題，也就是邊界問題。二分法，首先要確定答案一定在一個L——R的范圍之中，通過枚舉中間的位置，確定答案一定在左右兩段區間中的某一邊，然后通過刪掉其中的一邊，答案的范圍就縮小為原來的一半。

適用二分法題目所具有的特點：

70% 的二分法的題目都和單調性有關系（題目中告訴我們某種性質是單調的）。也就是說單調性和二分法沒有直接的關系：有單調性的題目基本上都可以利用二分法，但是可以用二分法的題目不一定非得有單調性。

95% 的可以用二分法的題目有一個本質的性質：存在兩段性的性質；在這個區間里面，一個性質在其中的一段上面是成立的，在另一段上面是不成立的。

剩下的5%的可以用二分法來做的題目是沒有規律可言的。

二分法的兩種模版是針對于下面這兩種情況的：

看到這個上面的圖的時候，需要注意理解一下幾個點：

A這個點是滿足紅色性質的最后一個點（整數二分的話，就代表一個數值）；B這個點是滿足綠色性質的第一個點

L、M、R 分別表示開始、中間和結束點

模版一：當要二分的答案在綠色的區間段的時候：

首先，我們二分綠色上的 B 這個點，那么就有以下幾種情況了：
① if M 是綠色的，而我們想要的點 B 在 M 的左側（這個地方直接看圖去理解比較好），所以區間由 [ L——R ] 變成了 [ L——M ] ，并且這個 M 是包含的；② else M 是紅色的，區間 [ L——R ] 變成 [ M+1——R ] ,這個對應著模版一：

int bsearch_1(int l, int r) {while(l < r){int mid = l + r >> 1;//可以寫成 mid = (l + r + ) >> 1if (check(mid)) r = mid;else l = mid + 1;}return 1; }

模版二：當要二分的答案在紅色的區間段的時候：

首先，我們二分紅色上的 A 這個點，那么就有以下幾種情況了：
① if M 是紅色的，而我們想要的點 A 在 M 的右側（這個地方直接看圖去理解比較好），所以區間由 [ L——R ] 變成了 [ M——R ] ，并且這個 M 是包含的；② else M 是綠色的，要找的點在M的左側，并且M肯定不是我們要找的點，區間 [ L——R ] 變成 [ L——M-1 ] ,這個對應著模版二：

int bsearch_2(int l, int r) {while(l < r){int mid = l + r + 1 >> 1;//可以寫成 mid = (l + r + 1) >> 1if (check(mid)) l = mid;else r = mid - 1;}return l; }

模版一和模版二唯一的一個區別是，模版一在計算中間點的時候是下取整，模版二在計算中間結點的時候是上取整，兩個模版都少了一個括號，這里存在著一個C++的一個語法：+的優先級比右移的優先級運算要高。

為什么模版二在計算mid的時候多加了1？

現在來講一個，為什么我們在計算模版二的時候需要啥進行上取整？也就是上面要進行一個加 1 的操作，是因為我們的更新方式所決定的，要考慮邊界情況。首先是，假設 L=R-1 ，那么我們在計算中間結點的時候：M = L+R，除以2之后下取整，即等于 L，如下：

即看看我們之前的假設，假設M是紅顏色的，那么更新的時候應該是[L,R]->[M,R],而在剛剛沒有進行上取整（也就是說沒有進行加1操作之后），這個區間更新之后是沒有變化的，所以說，這里是要進行上取整。

總結：

Tip：與 M 相關的三個點，總是先賦值給那個小的，但是賦值給 L 還是 R，在模版一中（綠色），往前走，R被先賦值；在模版的二中（紅色），往后走，L被先賦值。

總結

以上是生活随笔為你收集整理的二分查找思想以及模版的套用的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。