1. 循環(huán)法
public static int binarySearch(int[] arr, int low, int high, int target) {
while (low <= high) {
// 這樣寫(xiě)主要是避免溢出的情況，以及>>優(yōu)先級(jí)小于+，避免出現(xiàn)死循環(huán)
int mid = low + ((high - low) >> 1);
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}
2. 遞歸
public static int binarySearch1(int[] array, int low, int high, int target) {
if (low < high) {
int mid = low + ((high - low) >> 1);
if (array[mid] == target) {
return mid;
} else if (array[mid] > target) {
return binarySearch(array, low, mid - 1, target);
} else {
return binarySearch(array, mid + 1, high, target);
}
}
return -1;
}
3. 元素中有重復(fù)的二分查找
假設(shè)現(xiàn)在有個(gè)數(shù)組里面有重復(fù)元素，并且按照增序排列，如果有相同元素，返回最左側(cè)的第一個(gè)重復(fù)元素的位置。文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-643569.html
核心思路也是比較簡(jiǎn)單了，當(dāng)找到第一個(gè)重復(fù)的元素時(shí)候，記錄位置，然后向左移動(dòng)，左邊的不是目標(biāo)元素，就意味著左邊沒(méi)有重復(fù)的目標(biāo)元素，然后+1就是目標(biāo)元素的位置文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-643569.html
public static int search(int[] nums, int target) {
if (nums == null || nums.length == 0)
return -1;
int low = 0;
int high = nums.length - 1;
while (low <= high) {
int mid = low + ((high - low) >> 1);
if (nums[mid] < target) {
low = mid + 1;
} else if (nums[mid] > target) {
high = mid - 1;
} else {
// 找到了符合目標(biāo)元素的數(shù)據(jù)位置,然后一直往左遍歷，知道不是目標(biāo)元素或者索引為0的時(shí)候停止
while (mid != 0 && nums[mid] == target) {
mid--;
}
if (mid == 0 && nums[mid] == target) {
return mid;
}
return mid + 1;
}
}
return -1;
}
到了這里，關(guān)于算法通關(guān)村——透徹理解二分查找的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
