- 二分查找算法介紹
- 二分查找算法的思路分析
- 二分查找算法(非遞歸)代碼實(shí)現(xiàn)
- 二分查找算法(遞歸)代碼實(shí)現(xiàn)
- 查找數(shù)組中只有一個(gè)結(jié)果的
- 查找數(shù)組中有多個(gè)結(jié)果的
1. 二分查找算法(非遞歸)介紹
- 二分查找法只使用從有序的數(shù)列中進(jìn)行查找(比如數(shù)字或字母等)，將數(shù)列排序后再進(jìn)行查找
- 二分查找的運(yùn)行時(shí)間為
O(log2 n)连茧，即查找到的目標(biāo)位置最多只需要log2 n步 。
2.二分查找算法的思路分析
- 思路分析
首先確定數(shù)組的中間的下標(biāo)
mid=(left+right)/2然后讓需要查找的數(shù) findVal 和 arr[mid] 比較
2.1
findVal > arr[mid],說明查找的數(shù)在 mid 的右邊，需要遞歸向右查找 或 右移查找2.2
findVal < arr[mid], 說明查找的數(shù)在 mid 的左邊，需要遞歸向左查找 或 左移查找2.3
findVal == arr[mid]强衡，說明找到譬涡，就返回
- 什么時(shí)候結(jié)束遞歸或循環(huán)
- 找到就結(jié)束
- 遞歸完整個(gè)數(shù)組，仍沒有找到击敌，當(dāng)
left > right就退出
3. 二分查找算法(非遞歸)代碼實(shí)現(xiàn)
public class BinarySearchNoRecur {
public static void main(String[] args) {
//測(cè)試
int[] arr = {1,3,8,10,11,67,100};
int index = binarySearch(arr,9);
System.out.println("index=" + index); //
}
/**
* 二分查找的非遞歸實(shí)現(xiàn)
* @param arr 待查找的數(shù)組，arr是升序排序
* @param target 需要查找的數(shù)
* @return 返回對(duì)應(yīng)下標(biāo)拴事，-1表示沒有找到
*/
public static int binarySearch(int[] arr,int target){
int left = 0;
int right = arr.length - 1;
while(left <= right){ //說明可以繼續(xù)查找
int mid = (left + right) / 2;
if(arr[mid] == target){
return mid;
}else if(arr[mid] > target){
right = mid - 1; //需要左移查找
}else if(arr[mid] < target){
left = mid + 1; //需要向右邊查找
}
}
return -1;
}
}
4.二分查找算法(遞歸)代碼實(shí)現(xiàn)
4.1查找數(shù)組中只有一個(gè)結(jié)果的
/**
* 二分查找法(只能找到一個(gè)結(jié)果)
* @param arr 數(shù)組
* @param left 左邊的索引
* @param right 右邊的索引
* @param findVal 要查找的值
* @return 如果找到就返回下標(biāo)沃斤，如果沒有找到，就返回-1
*/
public static int binarySearch(int[] arr,int left,int right,int findVal){
if(left > right){
return -1;
}
int mid = (left + right) / 2;
int midVal = arr[mid];
if(findVal > midVal){ //向右遞歸
return binarySearch(arr,mid+1,right,findVal);
}else if(findVal < midVal){ //向左遞歸
return binarySearch(arr,left,mid - 1,findVal);
}else { //找到了
return mid;
}
}
4.2 查找數(shù)組中有多個(gè)結(jié)果的
//將有序數(shù)組中的所有數(shù)值都查找到
//思路：
//1. 在找到 mid 索引值刃宵，不要馬上返回
//2. 向 mid 索引的左邊掃描衡瓶，將所有滿足1000 的元素的下標(biāo)，加入到集合ArrayList
//3. 向 mid 索引的右邊掃描牲证， 將所有滿足1000 的元素的下標(biāo)哮针，加入到集合 ArrayList
//4. 返回ArrayList
public static List<Integer> binarySearch2(int[] arr, int left, int right, int findVal){
if(left > right){
return new ArrayList<>();
}
int mid = (left + right) / 2;
int midVal = arr[mid];
if(findVal > midVal){ //向右遞歸
return binarySearch2(arr,mid+1,right,findVal);
}else if(findVal < midVal){ //向左遞歸
return binarySearch2(arr,left,mid - 1,findVal);
}else { //找到了
List<Integer> resIndexList = new ArrayList<>();
//向 mid 索引的左邊掃描，將所有滿足1000 的元素的下標(biāo)，加入到集合ArrayList
int temp = mid - 1;
while (true){
if(temp < 0 || arr[temp] != findVal){
break;
}
//否則十厢，就把temp放入 resIndexList
resIndexList.add(temp);
temp -= 1; //將temp 左移
}
resIndexList.add(mid);
//向 mid 索引的右邊掃描等太， 將所有滿足1000 的元素的下標(biāo)，加入到集合 ArrayList
temp = mid + 1;
while (true){
if(temp > arr.length-1 || arr[temp] != findVal){
break;
}
//否則蛮放，就把temp放入 resIndexList
resIndexList.add(temp);
temp += 1; //將temp 左移
}
return resIndexList;
}
