位運(yùn)算
除法在計(jì)算機(jī)中效率很低，一般改用 >> x ，意思是二進(jìn)制數(shù)的每個(gè)位右移 x 位。從十進(jìn)制的角度看， x 是以 2 為底的指數(shù)，這個(gè)指數(shù)就是除數(shù)。文章來源：http://www.zghlxwxcb.cn/news/detail-813971.html
//等價(jià)式
mid = (low + high) / 2;
mid = low + high >> 2; //效率提高
mid = low + (high - low >> 2); //防止(low + high)溢出
在 Java 中，位運(yùn)算符 >> 的優(yōu)先級(jí)低于加法運(yùn)算符 +，所以需要使用括號(hào)來保證正確的優(yōu)先級(jí)文章來源地址http://www.zghlxwxcb.cn/news/detail-813971.html
用遞歸實(shí)現(xiàn)二分查找
/**
* @param arr 升序數(shù)組
*/
public static int binarySearch(int[] arr, int low, int high, int target)
{
if(low > high)
return -1; //沒有找到返回-1
int mid = low + (high - low >> 1);
if(arr[mid] == target)
return mid; //返回目標(biāo)值的位置
else if(arr[mid] < target)
return binarySearch(arr,mid + 1, high, target); //向右尋找
else
return binarySearch(arr, low, mid - 1, target); //向左尋找
}
有重復(fù)元素的二分查找
迭代實(shí)現(xiàn)
public static int binarySearch(int[] arr, int target)
{
int low = 0;
int high = arr.length - 1;
// 使用二分查找法查找target
while (low <= high)
{
int mid = low + (high - low >> 1);
// 如果中間元素等于target，則返回中間元素索引
if (arr[mid] == target)
{
// 如果中間元素不是第一個(gè)元素，則繼續(xù)向前查找
while (mid != 0 && arr[mid] == target)
mid--;
// 如果中間元素是第一個(gè)元素，則返回0
if (mid == 0)
return 0;
else
return mid + 1;
}
// 如果中間元素小于target，則將low移動(dòng)到mid+1
else if (arr[mid] < target)
low = mid + 1;
// 如果中間元素大于target，則將high移動(dòng)到mid-1
else
high = mid - 1;
}
// 如果查找結(jié)束沒有找到target，則返回-1
return -1;
}
到了這里，關(guān)于逢試必考的二分查找（算法村第九關(guān)青銅挑戰(zhàn)）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
