二分查找
- 什么是二分查找
- 實(shí)現(xiàn)原理
什么是二分查找
二分查找是從一個(gè)有序數(shù)組中找到目標(biāo)元素（通常是找下標(biāo)）的過(guò)程
實(shí)現(xiàn)原理
先來(lái)看兩張圖
圖例1
image
圖例2
image
nums:有序數(shù)組
fromIndex：起始指針点把，跟toIndex一起確定查找范圍
toIndex:結(jié)束指針送矩，結(jié)合fromIndex確定查找范圍
mid：中間指針，指向查找范圍中間位置的指針
midValue:中間指針指向元素的值
- 查找過(guò)程：
首先指定查找范圍是整個(gè)數(shù)組偶器，然后找到中間指針指向的元素（midVal）的值跟目標(biāo)值（如target）進(jìn)行比對(duì)，如果midVal小于target抑片，fromIndex指針從mid位置向右移動(dòng)一位(圖例2)仇味，反之toIndex從mid位置向左移動(dòng)一位，重新確定查找范圍蛇受，繼續(xù)重復(fù)上述操作直到找到target等于midVal或者fromIndex>toIndex查找結(jié)束
代碼實(shí)現(xiàn)：
public static int binarySearch(int[] nums, int target) {
int fromIndex = 0;
int toIndex = nums.length - 1;
while (fromIndex <= toIndex) {
int mid = (fromIndex + toIndex) >> 1;
int midVal = nums[mid];
if (midVal < target) {
fromIndex = mid + 1;
} else if (midVal > target) {
toIndex = mid - 1;
} else {
return mid;
}
}
return -1;
}
