快捷導(dǎo)航

一篇文章帶你了解C語言二分查找的簡單應(yīng)用

更新時(shí)間：2021年08月31日 15:02:29 作者：Outsider373

這篇文章主要介紹了二分查找算法在C語言程序中的使用示例,文中最后提到了使用二分查找法一個(gè)需要注意的地方,需要的朋友可以參考下

前言

在有序數(shù)組中查找具體的某個(gè)數(shù)字n，可能有同學(xué)會說一個(gè)一個(gè)找，但是這樣的效率實(shí)在太低，特別是對于有序的數(shù)組，效率太低。我們一般從中間元素開始找，查一次去掉一半數(shù)字，這種方法我們給它取名為折半查找即為二分查找，效率大大提高！怎么理解呢？如果有2的32次方個(gè)數(shù)字，我們最多只需查找32次，而一個(gè)一個(gè)數(shù)運(yùn)氣不好卻是2的32次方次。

實(shí)戰(zhàn)演練

這里我們先給出所寫代碼以及運(yùn)行結(jié)果

在這里，給大家分析一下，首先，我們先創(chuàng)建一個(gè)有序數(shù)組arr[],然后我們把要查找的7用int k表示，我們要確定這組數(shù)組的左下標(biāo)0，右下標(biāo)為sz-1，sz為數(shù)組的元素個(gè)數(shù)，即int left = 0,int right = sz-1;我們還要計(jì)算一下數(shù)組的元素總個(gè)數(shù)int sz =sizeof(arr)/sizeof(arr[0]);然后我們還需找出平均值int mid,如果arr[mid] < k,此時(shí)左下標(biāo)left = mid+1，當(dāng)arr[mid] > k,右下標(biāo)right = mid-1,最后只剩一種情況直接打印break;出我們要求的mid，但是這只是一次查找，但是真正的二分查找需要好多次，那我們就需要讓它循環(huán)while起來，需要一個(gè)條件left<=right,這說明中間還有元素，直到我們找到，但是當(dāng)left>right時(shí)，此時(shí)我們可以大膽說明找不到，具體的代碼如上圖所示，這便是整個(gè)過程。小伙伴們趕緊int main(),return 0;敲起來試一試吧。

在這里，我在介紹另一種方法，通過函數(shù)的調(diào)用實(shí)現(xiàn)我們的二分查法。

這里的思路主要跟上一種方法的思路差不多，在這里說明一下不能用0 == ret，雖然說0為假，非0為真，但是在這組數(shù)組中1的下標(biāo)就是為0，在這里提醒一下各位，另外，千萬不能不傳sz，即不能把int sz放在函數(shù)那一塊區(qū)域里求，這種寫法是有問題的，什么問題呢？這里簡單說明一下，問題在于此時(shí)求的sz不是10，而是1，為什么？數(shù)組arr傳參，實(shí)際傳遞的不是數(shù)組的本身，僅僅傳過去了數(shù)組首元素的地址，即為a的指針，實(shí)際上int a[]只是掛羊皮賣狗肉，本質(zhì)上是指針，所以在函數(shù)不能在函數(shù)內(nèi)部求，根本求不出元素個(gè)數(shù)，另外，在int a []不需要寫數(shù)字大小，沒有意義，希望大家能夠理解，int a []并不會真正創(chuàng)建一個(gè)數(shù)組，大家一定要注意，未來如果我們遇到函數(shù)內(nèi)部需要參數(shù)部分傳過來元素個(gè)數(shù)，一定是在外部求好元素個(gè)數(shù)的，大家一定要多加注意，即在函數(shù)內(nèi)部求元素個(gè)數(shù)是做不到的。

思路分析

最后，在這里總結(jié)一下思路，進(jìn)行思路分析，二分查找是要求所查找數(shù)組的順序必須是有序的，我們定義left為最左端的元素，right為最右端的元素，mid=（left+right)/2為數(shù)組的中間位置，然后用所查找的值的位置與mid所處的位置進(jìn)行比較，如果比mid小，只需在數(shù)組的前半部分查找，如果比mid大，在數(shù)組的后半部分查找，以此類推，直到查到到所尋找的值不在該數(shù)組為止，這便是整體的思路。