結(jié)論

對(duì)n個(gè)元素進(jìn)行二分查找，最大比較次數(shù)為：$?lo{g}_{2}n?+1$

問(wèn)題

給定升序數(shù)組，各元素不同，查找某元素。
如果該元素存在：輸出該元素的下標(biāo)
如果不存在該元素，輸出-1
算法思路：

• 對(duì)于有序數(shù)列（從小到大），設(shè)定左端l（最小元素下標(biāo)）和右端r（最大元素下標(biāo)）
• 當(dāng)滿足條件l <= r時(shí)，求中點(diǎn)m，將中點(diǎn)元素的值與所要查找的值比較
• 若中點(diǎn)元素值比所要查找元素小，則應(yīng)找后半段，所以l = m+1，否則應(yīng)找前半段r = m - 1
• 重復(fù)以上過(guò)程，直到找到為止，若l > r，則說(shuō)明找不到。
  代碼：

//輸入n，輸入n個(gè)數(shù)（升序，各不相同），輸入x，求x是第幾個(gè)數(shù) #include <bits/stdc++.h> using namespace std; int main() {int n, a[1005], x, l, r, m;cin >> n;for(int i = 1; i <= n; ++i)cin >> a[i];cin >> x;l = 1, r = n;while(l <= r)//l在r左邊 {m = (l + r) / 2;//取中點(diǎn)位置 if(x > a[m])//如果x在右半部分 l = m + 1;//l移到中點(diǎn)右邊 else if(x < a[m])//如果x在左半部分 r = m - 1;//r移到中點(diǎn)左邊 else{cout << m;//如果中點(diǎn)是要查找的數(shù)字，那么輸出該位置 return 0;}}cout << -1;//沒(méi)找到，輸出-1 return 0; }

二分查找的最大比較次數(shù)

按上述算法進(jìn)行二分查找，證明二分查找的最大查找次數(shù)
引理1：如果k為偶數(shù)，且$k\ge 1$，那么$?lo{g}_{2}k?=?lo{g}_2(k+1)?$
證明：
設(shè)x = $?lo{g}_{2}k?$，則有$x\le lo{g}_{2}k<x+1$
只需證明$x\le lo{g}_2(k+1)<x+1$，即可證明$?lo{g}_{2}k?=?lo{g}_2(k+1)?$

$lo{g}_{2}k<x+1?k<2^{x+1}$
由于k和$2^{x+1}$都是整數(shù)，所以有$k+1\le 2^{x+1}$
而k是偶數(shù)，k+1是奇數(shù)，$2^{x+1}$一定是偶數(shù)，所以不可能滿足$k+1=2^{x+1}$
所以有$k+1<2^{x+1}?lo{g}_2(k+1)<x+1$
易知：$x\le lo{g}_{2}k<lo{g}_2(k+1)$
所以$x\le lo{g}_2(k+1)<x+1$，該引理得證。

證明對(duì)n個(gè)元素進(jìn)行二分查找，最大比較次數(shù)為：$?lo{g}_{2}n?+1$

證明：用數(shù)學(xué)歸納法
已知n為2時(shí)，找第1個(gè)元素需要比較1次，找第2個(gè)元素需要比較2次，最大查找2次，滿足$?lo{g}_{2}n?+1$
假設(shè)$2\le n\le k$時(shí)，最大查找次數(shù)為$?lo{g}_{2}k?+1$，證明：n為k+1時(shí)最大查找次數(shù)為$?lo{g}_2(k+1)?+1$
$n=k+1$時(shí)，進(jìn)行一次二分查找后，下一次要查找的長(zhǎng)度為：

• 如果k+1為偶數(shù)，下一次查找的長(zhǎng)度為$\frac{k+1}{2}$，查找這一段的最大查找次數(shù)為$?lo{g}_2\frac{k+1}{2}?+1=?lo{g}_2(k+1)?$，加上剛剛進(jìn)行的一次查找，最大查找次數(shù)為：$?lo{g}_2(k+1)?+1$
• 如果k+1為奇數(shù)，下一次查找的長(zhǎng)度為k/2，查找這一段的最大查找次數(shù)為：$?lo{g}_2\frac{k}{2}?+1=?lo{g}_{2}k?$ ，當(dāng)k+1為奇數(shù)即k為偶數(shù)時(shí)，根據(jù)引理1有：$?lo{g}_{2}k?=?lo{g}_2(k+1)?$，加上剛剛進(jìn)行的一次查找，最大查找次數(shù)為：$?lo{g}_2(k+1)?+1$

原命題得證。

總結(jié)

以上是生活随笔為你收集整理的二分查找最大比较次数证明的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。