前言

成都創(chuàng)新互聯(lián)公司自成立以來(lái)，一直致力于為企業(yè)提供從網(wǎng)站策劃、網(wǎng)站設(shè)計(jì)、成都做網(wǎng)站、成都網(wǎng)站建設(shè)、電子商務(wù)、網(wǎng)站推廣、網(wǎng)站優(yōu)化到為企業(yè)提供個(gè)性化軟件開發(fā)等基于互聯(lián)網(wǎng)的全面整合營(yíng)銷服務(wù)。公司擁有豐富的網(wǎng)站建設(shè)和互聯(lián)網(wǎng)應(yīng)用系統(tǒng)開發(fā)管理經(jīng)驗(yàn)、成熟的應(yīng)用系統(tǒng)解決方案、優(yōu)秀的網(wǎng)站開發(fā)工程師團(tuán)隊(duì)及專業(yè)的網(wǎng)站設(shè)計(jì)師團(tuán)隊(duì)。

一、二分查找的原理

二、二分查找的代碼C語(yǔ)言實(shí)現(xiàn)

總結(jié)

不知道大家有沒(méi)有聽過(guò)諸葛亮問(wèn)十個(gè)問(wèn)題猜將士心中數(shù)字問(wèn)題這個(gè)故事。傳說(shuō)中諸葛亮猜數(shù)的故事諸葛亮召集將士，讓他們從1-1024中選出一個(gè)整數(shù)記在心里。然后諸葛亮?xí)?wèn)他們10個(gè)問(wèn)題，他們只需回答：“是”或“不是”，最終諸葛亮就能得出他們心中所想是數(shù)。如問(wèn)一謀士：“你選的數(shù)大于512？”謀士答：“不是”，之后9個(gè)問(wèn)題過(guò)后，諸葛亮得出謀士所選的數(shù)是1，謀士大為吃驚，這的確是他想的數(shù)。諸葛亮所使用的方法就是把1024一半一半地取，取到第十次時(shí)就是1。根據(jù)這個(gè)原理去提10個(gè)問(wèn)題就能找到別人心中所想的數(shù)。而這個(gè)原理就是我下面要介紹的二分查找也叫折半查找。

1. 首先定義一個(gè)有序數(shù)組；

2.然后定義左區(qū)間left:數(shù)組下標(biāo)0，和右區(qū)間:大數(shù)組下標(biāo)。

3.取中間位mid:mid=(left+right)/2

4.判斷mid與目標(biāo)元素target的大小，一共有三種情況:

(1)若target>arr[mid]; 則將left=mid+1;?

(2)若target

(3)若target==arr[mid]; 則返回查找成功;

5.當(dāng)判斷循環(huán)left>right時(shí)推出循環(huán)，并且返回此數(shù)不在數(shù)組內(nèi)。?

int BinarySearch(int arr[],int len,int target)
{
?? ?int left = 0;//左下標(biāo)
?? ?int right = len - 1;//右下標(biāo)
?? ?while (left<= right)
?? ?{
?? ??? ?//int mid = (left + right) / 2;這樣有可能會(huì)出現(xiàn)兩個(gè)很大的數(shù)值相加超過(guò)整形范圍
        int mid=(right-left)/2+left;
?? ??? ?if (target >arr[mid])
?? ??? ?{
?? ??? ??? ?left = mid + 1;
?? ??? ?}
?? ??? ?else if (target< arr[mid])
?? ??? ?{
?? ??? ??? ?right = mid - 1;
?? ??? ?}
?? ??? ?else
?? ??? ?{
?? ??? ??? ?return mid;
?? ??? ?}
?? ?}
?? ?return -1;
}
int main()
{

?? ?int target = 0;
?? ?int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
?? ?int len = sizeof(arr) / sizeof(arr[0]);//獲取數(shù)組元素個(gè)數(shù)
?? ?scanf("%d", &target);
?? ?int index = BinarySearch(arr, len, target);
?? ?if (index != -1)
?? ??? ?printf("找到元素，下標(biāo)為%d\n", index);
?? ?else
?? ??? ?printf("未找到\n");
?? ?return 0;
}

二分查找的速度還是特別快的，但是唯一的缺點(diǎn)就是需要數(shù)組是有序的。初學(xué)者容易犯兩個(gè)錯(cuò)誤。第一個(gè)是判斷循環(huán)的條件一定是left<=right; 第二個(gè)是誤將mid的定義放在循環(huán)外邊。

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧