1、二分查找概念

海港ssl適用于網(wǎng)站、小程序/APP、API接口等需要進行數(shù)據(jù)傳輸應(yīng)用場景，ssl證書未來市場廣闊！成為成都創(chuàng)新互聯(lián)公司的ssl證書銷售渠道，可以享受市場價格4-6折優(yōu)惠！如果有意向歡迎電話聯(lián)系或者加微信：18982081108（備注：SSL證書合作）期待與您的合作！

二分查找又稱折半查找，優(yōu)點是比較次數(shù)少，查找速度快，平均性能好；其缺點是要求待查表為有序表，且插入刪除困難。因此，折半查找方法適用于不經(jīng)常變動而查找頻繁的有序列表。首先，假設(shè)表中元素是按升序排列，將表中間位置記錄的關(guān)鍵字與查找關(guān)鍵字比較，如果兩者相等，則查找成功；否則利用中間位置記錄將表分成前、后兩個子表，如果中間位置記錄的關(guān)鍵字大于查找關(guān)鍵字，則進一步查找前一子表，否則進一步查找后一子表。重復(fù)以上過程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時查找不成功。

2、二分查找簡單實現(xiàn)

（1）左開右閉 【 ）

//非遞歸版本
int* BinarySearch(int *a,int n,int key)
{
	if (a==NULL||n==0)
	{
		return NULL;
	}
	//[)
	int left=0;
	int right=n;
	while(left<right) //如果寫成left<=right 有可能越界
	{
		int mid=left+(right-left)/2;
		if (a[mid]>key)
		{
			right=mid;     
			//如果寫成right=mid+1 元素如果是a[0]=0，a[1]=1,要找1
			//left=0，right=1，mid=0
			//然后a[mid]<1,right=mid;此時找不到1，因為left<right
			//所以當(dāng)為【）不要把未判斷元素直接做right的下標(biāo)
		}
		else if(a[mid]<key)
		{
			left=mid+1;
		}
		else
		{
			return a+mid;
		}
	}
	return NULL;
}
void testBinary()
{
	int a[10]={0,1,3,5,45,78,98,111,121,454};
	for (int i=9;i>=0;i--)
	{
		int *temp=BinarySearch(a,10,i);
		if(temp==NULL)
		{
			cout<<"NULL"<<endl;
		}
		else
			cout<<*temp<<endl;
	}
}
//遞歸版本
int * BinarySearch_R(int *a,int n,int key,int left,int right)
{
    if(a==NULL||n==0)
    {
        return NULL;
    }
    if(left<right)
    {
        int mid=left+(right-left)/2;
        if(a[mid]>key)
        {
            return BinarySearch_R(a,n,key,left,mid);
        }
        else if(a[mid]<key)
        {
            return BinarySearch_R(a,n,key,mid+1,right);
        }
        else
        {
            return a+mid;
        }
    }
    else
    {
        return NULL;
    }
}

void testBinary_R()
{
	int a[10]={0,1,3,5,45,78,98,111,121,454};
	for (int i=9;i>=0;i--)
	{
		int *temp=BinarySearch_R(a,10,i,0,10);
		if(temp==NULL)
		{
			cout<<"NULL"<<endl;
		}
		else
			cout<<*temp<<endl;
	}
}

（2）左閉右閉 【】

int* BinarySearch_C(int *a,int n,int key)
{
    if(a==NULL||n==0)
    {
        return NULL;
    }
    //[]
    int left=0;
    int right=n-1;
    while(left<=right)
    {
        int mid=left+(right-left)/2;
        if(a[mid]>key)
        {
            right=mid-1; //a[mid]的值已經(jīng)判斷過了
        }
        else if(a[mid]<key)
        {
            left=mid+1; //a[mid]已經(jīng)判斷過了
        }
        else
            return a+mid；
    }
    return NULL;
}

void testBinary()
{
	int a[10]={0,1,3,5,45,78,98,111,121,454};
	for (int i=9;i>=0;i--)
	{
		int *temp=BinarySearch_C(a,10,i);
		if(temp==NULL)
		{
			cout<<"NULL"<<endl;
		}
		else
			cout<<*temp<<endl;
	}
}

//遞歸版本
int * BinarySearch_CR(int *a,int n,int key,int left,int right)
{
    if(a==NULL||n==0)
    {
        return NULL;
    }
    if(left<=right)
    {
        int mid=left+(right-left)/2;
        if(a[mid]>key)
        {
            return BinarySearch_R(a,n,key,left,mid-1);
        }
        else if(a[mid]<key)
        {
            return BinarySearch_R(a,n,key,mid+1,right);
        }
        else
        {
            return a+mid;
        }
    }
    else
    {
        return NULL;
    }
}

void testBinary_R()
{
	int a[10]={0,1,3,5,45,78,98,111,121,454};
	for (int i=9;i>=0;i--)
	{
		int *temp=BinarySearch_CR(a,10,i,0,9);
		if(temp==NULL)
		{
			cout<<"NULL"<<endl;
		}
		else
			cout<<*temp<<endl;
	}
}

題目：

正整數(shù)數(shù)組a[0], a[1], a[2], ···, a[n-1]，n可以很大，大到1000000000以上，但是數(shù)組中每個數(shù)都不超過100?，F(xiàn)在要你求所有數(shù)的和。假設(shè)這些數(shù)已經(jīng)全部讀入內(nèi)存，因而不用考慮讀取的時間。希望你用最快的方法得到答案。

提示：二分。

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機、免備案服務(wù)器”等云主機租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。

網(wǎng)站標(biāo)題：有關(guān)二分查找的邊界思考-創(chuàng)新互聯(lián)
本文URL：http://aaarwkj.com/article4/ddoooe.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供域名注冊、網(wǎng)站策劃、面包屑導(dǎo)航、小程序開發(fā)、響應(yīng)式網(wǎng)站、品牌網(wǎng)站設(shè)計

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)