二分查找：
請對一個有序陣列進行二分查找 {1,8, 10, 89, 1000, 1234} ，輸入一個數看看該陣列是否存在此數，并且求出下 標，如果沒有就提示"沒有這個數"，
二分查找思路
二分查找核心代碼
public static int binarySearch(int[] arr, int left, int right, int findVal) {
/**
* @description:二分查找演算法
* @author: ma lin yan
* @date: 2022/11/6 20:45
* @param: [arr->陣列, left-->左邊的索引, right-->右邊的索引,
* findVal-->要查找的值]
* @return: int 如果找到就回傳下標，如果沒有找到，就回傳-1
**/
// 當 left > right 時，說明遞回整個陣列，但是沒有找到
if (left > right) {
return -1;
}
int mid = (left + right) / 2;
int midVal = arr[mid];
if (midVal < findVal) {//向右遞回
return binarySearch(arr, mid + 1, right, findVal);
} else if (midVal > findVal) {
//向左遞回
return binarySearch(arr, left, mid - 1, findVal);
} else {
return mid;
}
}
陣列中滿足條件不止一個
說明：增加了找到所有的滿足條件的元素下標:
課后思考題： {1,8, 10, 89, 1000, 1000，1234} 當一個有序陣列中，有多個相同的數值時，如何將所有的數值 都查找到，比如這里的 1000.
核心代碼：
//完成一個課后思考題:
/*
* 課后思考題： {1,8, 10, 89, 1000, 1000，1234} 當一個有序陣列中，
* 有多個相同的數值時，如何將所有的數值都查找到，比如這里的 1000
*
* 思路分析
* 1. 在找到mid 索引值，不要馬上回傳
* 2. 向mid 索引值的左邊掃描，將所有滿足 1000， 的元素的下標，加入到集合ArrayList
* 3. 向mid 索引值的右邊掃描，將所有滿足 1000， 的元素的下標，加入到集合ArrayList
* 4. 將Arraylist回傳
*/
public static List<Integer> binarySearch2(int[] arr, int left, int right, int findVal) {
//當left > right 時,說明遞回整個陣列，沒有找到
if (left > right) {
return new ArrayList<Integer>();
}
int mid = (left + right) / 2;
int midVal = arr[mid];
if (midVal < findVal) {
//向右遞回
return binarySearch2(arr, mid + 1, right, findVal);
} else if (midVal > findVal) {
//向左遞回
return binarySearch2(arr, left, mid - 1, findVal);
} else {
// * 思路分析
// * 1. 在找到mid 索引值，不要馬上回傳
// * 2. 向mid 索引值的左邊掃描，將所有滿足 1000， 的元素的下標，加入到集合ArrayList
// * 3. 向mid 索引值的右邊掃描，將所有滿足 1000， 的元素的下標，加入到集合ArrayList
// * 4. 將Arraylist回傳
List<Integer> resIndexlist = new ArrayList<Integer>();
//將mid索引值左邊掃描，將滿足1000的元素下標，加入到集合ArrayList
int temp = mid - 1;
while (true) {
if (temp < 0 || arr[temp] != findVal) {
//退出
break;
}
//否則，把temp放入到ArrayList
resIndexlist.add(temp);
temp = -1;//temp向左移動
}
resIndexlist.add(mid);//
//將mid索引值右邊掃描，將滿足1000的元素下標，加入到集合ArrayList
temp = mid + 1;
while (true) {
if (temp > arr.length - 1 || arr[temp] != findVal) {
//退出
break;
}
//否則，就temp 放入到resIndexlist
resIndexlist.add(temp);
temp += 1;//右移
}
return resIndexlist;
}
}
}
主程式：
public static void main(String[] args) {
int arr[] = {1, 8, 10, 89, 1000, 1000, 1234};
//
int resIndex = binarySearch(arr, 0, arr.length - 1, 1000);
System.out.println("resIndex=" + resIndex);
System.out.println("普通二分查找如上，升級后的二分查找如下（即能找到一個陣列中滿足條件的不同下標）");
List<Integer> resIndexList = binarySearch2(arr, 0, arr.length - 1, 1000);
System.out.println("resIndexList=" + resIndexList);
}
運行結果：
這篇博客是我在B站看韓順平老師資料結構和演算法的課時的筆記，記錄一下，防止忘記，也希望能幫助各位朋友，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/528713.html
標籤：Java