介紹:

二分查找算法（Binary Search）是一種在有序數組中查找目標元素的算法。
它的基本思想是通過將目標元素與數組的中間元素進行比較，從而將搜索范圍縮小一半。

• 如果目標元素等于中間元素，則搜索結束；
• 如果目標元素小于中間元素，則繼續在左半部分查找；
• 如果目標元素大于中間元素，則在右半部分查找。

通過不斷地將搜索范圍縮小一半，最終可以找到目標元素或確定目標元素不存在。

接下來通過例題介紹二分的不同寫法

例題:

輸入一個整數 n, 接下來一行輸入 n 個整數(保證整數序列有序), 最后輸入一個整數 m, 查找 m 在序列中的起始下標和結束下標

示例1:

輸入:

5
1 2 2 4 5
2

輸出:

1 2

解釋:

2 在序列中的起始和結束位置是下標 1 和 2

代碼講解:

二分代碼按照退出條件分為

1. while (l <= r)
2. while (l < r)

代碼中的所有 l 和 r 都是序列的左右閉區間

代碼中的所有 l + r >> 1 和 l + r + 1 >> 1 分別相當于 (l + r) / 2 和 (l + r + 1) / 2。>>是按位右移, 整數向右位移一位相當于除2

代碼中的所有 x, 都是目標值, 也就是要查找的值; 所有的 idx, 是答案, 也就是要查找數的起始下標或結束下標

先講第一種: while (l <= r), 在l > r時退出

// 查找起始下標
int l = 0, r = n - 1, idx = 0;
while (l <= r)
{int mid = l + r >> 1;  // 一分為3, [l, mid), [mid, mid], (mid, r]if (a[mid] < x) l = mid + 1;  // 如果當前中間值比 x 小, 需要去序列的右區間, 因為mid位置的數比 x 小, 那么左邊的區間(l, mid]的所有數都比 x 小else if (a[mid] > x) r = mid - 1;  // 同上else if (a[mid] == x)  // 等于答案時{idx = mid;r = mid - 1;  // 我們要找的時起始的下標, 雖然此時a[mid] == x, 但是mid的左邊可能還有等于x的值, 所以我們要繼續往左區間去找}
}// 查找結束下標(代碼中只有注釋的地方和上面的代碼不一樣)
int l = 0, r = n - 1, idx = 0;
while (l <= r)
{int mid = l + r >> 1;  // 一分為3, [l, mid), [mid, mid], (mid, r]if (a[mid] < x) l = mid + 1;  else if (a[mid] > x) r = mid - 1;  else if (a[mid] == x)  {idx = mid;l = mid + 1;  // 我們要找的時結束的下標, 雖然此時a[mid] == x, 但是mid的右邊可能還有等于x的值, 所以我們要繼續往右區間去找}
}

觀察上面代碼我們可以把a[mid] == x的情況跟其他兩種情況合并

// 查找起始下標
int l = 0, r = n - 1, idx = 0;
while (l <= r)
{int mid = l + r >> 1;  // 一分為3, [l, mid), [mid, mid], (mid, r]if (a[mid] < x) l = mid + 1;  else if (a[mid] >= x){idx = mid;r = mid - 1;  // 繼續往左區間找}
}// 查找結束下標
int l = 0, r = n - 1, idx = 0;
while (l <= r)
{int mid = l + r >> 1;if (a[mid] <= x){idx = mid;l = mid + 1;  // 繼續往右區間找}else if (a[mid] > x) r = mid - 1;
}

下面講第二種: while (l < r) 在l == r時退出

大家可以發現這種寫法不需要 idx 這個變量來記錄最終查找的x的起始下標或結束下標了, 因為最后l就是對應的起始下標或結束下標。（r等于l, 所以用r也行）

查找起始下標
int l = 0, r = n - 1;
while (l < r)
{int mid = l + r >> 1;  // 區間分成了兩個 [l, mid] 和 (mid, r]if (a[mid] < x) l = mid + 1;// 當a[mid] == x的時候, r一直往左, 所以當有多個相同的x的話, 會查找到第一個else if (a[mid] >= x) r = mid;  // 因為a[mid]可能 == x, 因為mid也可能滿足條件, 所以區間變成[l, mid]
}查找結束下標
int l = 0, r = n - 1, idx = 0;
while (l < r)
{				int mid = l + r + 1 >> 1;  // 區間分成了兩個 [l, mid) 和 [mid, r]if (a[mid] > x) r = mid - 1;// 當a[mid] == x的時候, l一直往右, 所以當有多個相同的x的話, 會查找到最后一個else if (a[mid] <= x) l = mid;  // 因為a[mid]可能 == x, 因為mid也可能滿足條件, 所以區間變成[mid, r]
}

接下來講一下第二種查找結束下標的時候 為什么是 mid = l + r + 1 >> 1，而不是 mid = l + r >> 1;
c++默認向0取整, 對于正整數你可以說是向下取整, 也就是 5 / 2 = 2,
當出現 l = r - 1 的時候, 此時 mid = (l + r) / 2 向下取整后等于 r - 1 , 如果此時進入了a[mid] <= x的分支, 那么 l = mid = r - 1, 這時會發現 l 沒有發生變化, 那么就會一直陷入死循環

先更到這里, 后面再補充

覺得寫的不錯的話, 點個贊吧