溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務(wù)條款》
您好，登錄后才能下訂單哦！
二分查找的思想：
假設(shè)數(shù)據(jù)是按升序排序的，對于給定值key，從序列的中間位置開始比較，如果當前位置值等于key，則查找成功；若key小于當前位置值，則在數(shù)列的前半段中查找；若key大于當前位置值則在數(shù)列的后半段中繼續(xù)查找，直到找到為止。
二分查找思想并不復(fù)雜，但是在寫代碼的時候一定要控制好邊界值。有兩種控制邊界值的方法，左閉右閉和左閉右開。
循環(huán)實現(xiàn):
int BinarySelect(int *a, int size, int key)
{
if (a == NULL || size == 0)
{
return -1;
}
int left = 0, right = size -1 ;//改成左閉右開 right=size;
while (left <=right) //改成左閉右開 left<right
{
int mid = left + (right - left) / 2;
if (a[mid] > key)
{
right = mid - 1; //改成左閉右開 right=mid;
}
else if (a[mid] < key)
{
left = mid + 1;
}
else
{
return mid;
}
}
return -1;
}遞歸實現(xiàn)：
int BinarySelect_R(int *a, int left, int right,int key)//此時傳的是左閉右閉區(qū)間
{
if (left > right)//如果right傳的是開區(qū)間,條件是>=
return -1;
int mid = left + (right - left) / 2;
if (a[mid] > key)
{
return BinarySelect_R(a,left,mid-1,key);//如果right傳的是開區(qū)間，此時第三個參數(shù)是mid
}
else if (a[mid] < key)
{
return BinarySelect_R(a, mid + 1, right, key);
}
else
return mid;
}免責聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點不代表本網(wǎng)站立場，如果涉及侵權(quán)請聯(lián)系站長郵箱：is@yisu.com進行舉報，并提供相關(guān)證據(jù)，一經(jīng)查實，將立刻刪除涉嫌侵權(quán)內(nèi)容。
億速云公眾號
手機網(wǎng)站二維碼