介紹:

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

• 如果目標(biāo)元素等于中間元素，則搜索結(jié)束；
• 如果目標(biāo)元素小于中間元素，則繼續(xù)在左半部分查找；
• 如果目標(biāo)元素大于中間元素，則在右半部分查找。

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

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

例題:

輸入一個(gè)整數(shù) n, 接下來一行輸入 n 個(gè)整數(shù)(保證整數(shù)序列有序), 最后輸入一個(gè)整數(shù) m, 查找 m 在序列中的起始下標(biāo)和結(jié)束下標(biāo)

示例1:

輸入:

5
1 2 2 4 5
2

輸出:

1 2

解釋:

2 在序列中的起始和結(jié)束位置是下標(biāo) 1 和 2

代碼講解:

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

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

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

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

代碼中的所有 x, 都是目標(biāo)值, 也就是要查找的值; 所有的 idx, 是答案, 也就是要查找數(shù)的起始下標(biāo)或結(jié)束下標(biāo)

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

// 查找起始下標(biāo)
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;  // 如果當(dāng)前中間值比 x 小, 需要去序列的右區(qū)間, 因?yàn)閙id位置的數(shù)比 x 小, 那么左邊的區(qū)間(l, mid]的所有數(shù)都比 x 小else if (a[mid] > x) r = mid - 1;  // 同上else if (a[mid] == x)  // 等于答案時(shí){idx = mid;r = mid - 1;  // 我們要找的時(shí)起始的下標(biāo), 雖然此時(shí)a[mid] == x, 但是mid的左邊可能還有等于x的值, 所以我們要繼續(xù)往左區(qū)間去找}
}// 查找結(jié)束下標(biāo)(代碼中只有注釋的地方和上面的代碼不一樣)
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;  // 我們要找的時(shí)結(jié)束的下標(biāo), 雖然此時(shí)a[mid] == x, 但是mid的右邊可能還有等于x的值, 所以我們要繼續(xù)往右區(qū)間去找}
}

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

// 查找起始下標(biāo)
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;  // 繼續(xù)往左區(qū)間找}
}// 查找結(jié)束下標(biāo)
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;  // 繼續(xù)往右區(qū)間找}else if (a[mid] > x) r = mid - 1;
}

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

大家可以發(fā)現(xiàn)這種寫法不需要 idx 這個(gè)變量來記錄最終查找的x的起始下標(biāo)或結(jié)束下標(biāo)了, 因?yàn)樽詈髄就是對(duì)應(yīng)的起始下標(biāo)或結(jié)束下標(biāo)。（r等于l, 所以用r也行）

查找起始下標(biāo)
int l = 0, r = n - 1;
while (l < r)
{int mid = l + r >> 1;  // 區(qū)間分成了兩個(gè) [l, mid] 和 (mid, r]if (a[mid] < x) l = mid + 1;// 當(dāng)a[mid] == x的時(shí)候, r一直往左, 所以當(dāng)有多個(gè)相同的x的話, 會(huì)查找到第一個(gè)else if (a[mid] >= x) r = mid;  // 因?yàn)閍[mid]可能 == x, 因?yàn)閙id也可能滿足條件, 所以區(qū)間變成[l, mid]
}查找結(jié)束下標(biāo)
int l = 0, r = n - 1, idx = 0;
while (l < r)
{				int mid = l + r + 1 >> 1;  // 區(qū)間分成了兩個(gè) [l, mid) 和 [mid, r]if (a[mid] > x) r = mid - 1;// 當(dāng)a[mid] == x的時(shí)候, l一直往右, 所以當(dāng)有多個(gè)相同的x的話, 會(huì)查找到最后一個(gè)else if (a[mid] <= x) l = mid;  // 因?yàn)閍[mid]可能 == x, 因?yàn)閙id也可能滿足條件, 所以區(qū)間變成[mid, r]
}

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

先更到這里, 后面再補(bǔ)充

覺得寫的不錯(cuò)的話, 點(diǎn)個(gè)贊吧