目錄
- 1. 經典二分例題
- 2. 拓展例題一：尋找大于等于某數最左側位置
- 3. 拓展例題二：區域最小值問題
參考鏈接：2021最新左神資料結構演算法全家桶
1. 經典二分例題
題目一：在一個有序陣列中，找到某個數是否存在
1?? 如果采用暴力法，時間復雜度為O(N)
public static int findNum(int[] arr, int num) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == num)
return i;
}
return -1;
}
2?? 可以采用二分法，時間復雜度為O(log2N)（可以理解為每次砍一半，需要砍幾次，例如N=8，需要砍三次到1）
public static int binaryFindNum(int[] arr, int left, int right, int num) {
if (left > right)//遞回結束
return -1;
int mid = (left + right) / 2;
int midVal = arr[mid];
if (num > midVal)
return binaryFindNum(arr, mid + 1, right, num);//向右遞回
else if (num < midVal)
return binaryFindNum(arr, left, mid - 1, num);//向左遞回
else
return mid;
}
2. 拓展例題一：尋找大于等于某數最左側位置
題目：在一個有序陣列中，找大于等于某數最左側的位置
該題目仍然可以用二分法來解決，由于陣列有序，首先判斷陣列的中間數是否大于指定數，如果大于等于則繼續在右半邊尋找，如果小于則從左半邊尋找；然后在半邊部分繼續使用二分，直到無法二分為止，所找到的位置就是所求位置，如下圖案例所示：
代碼如下：
public static int binary(int[] arr, int left, int right, int num) {
if (left > right)//遞回結束
return -1;
int mid = (left + right) / 2;
int midVal = arr[mid];
//如果當前中間值>=num且左邊元素也>=num,則向左遞回
if (mid - 1 >= 0 && midVal >= num && arr[mid - 1] >= num)
return binary(arr, left, mid - 1, num);//向左遞回
//如果當前中間值>=num但左邊元素<num,則直接回傳該中間值
else if (mid - 1 >= 0 && midVal >= num && arr[mid - 1] < num)
return mid;
//其他情況向右遞回
else
return binary(arr, mid + 1, right, num);//向右遞回
}
由此可見，不僅僅是找一個數存不存在可以用二分，找>=某數最左側位置或者<=某數最右側位置都可以用二分
3. 拓展例題二：區域最小值問題
題目：在一個無序陣列中，任何兩個相鄰的數不相等，求一個區域最小的位置，規定時間復雜度小于O(N)
區域最小的定義如下：
- 對于0位置即陣列的第一個元素，如果該數小于1位置的數，則0位置為區域最小位置
- 對于n-1位置即陣列最后一個元素，如果該數小于n-2位置的數，則n位置為區域最小位置
- 對于陣列中間i元素，如果它小于i-1位置的數同時也小于i+1位置的數，則i位置為區域最小位置
思路：首先判斷0位置是不是區域最小，是則直接回傳；然后判斷1位置是不是區域最小，是則直接回傳；如果0位置和1位置都不是區域最小，該情況如下圖所示，則中間元素必然存在區域最小，分析如下：
0位置>1位置，所以0指向1箭頭向下，n-2位置<n-1位置，所以n-1指向n-2箭頭向下，由于陣列中兩兩元素不相等，所以每相鄰兩元素間都有如圖所示的箭頭，而由于進是一個向下的方向，出是一個向上的方向，因此中間必然存在一個低谷，即區域最小
那怎么找到區域最小的位置呢？我們同樣可以用二分來解決，首先取陣列中間元素M，如果M為區域最小，則直接回傳，否則假設M>M-1的位置，則M到M-1為一個向下的箭頭，則按照上面的分析，由于0位置和M-1位置的方向相反，則``0M-1`區間必然存在區域最小，則我們繼續在`0M-1`區間二分，依次類推，不斷二分直到中間位置為區域最小回傳即可
代碼如下：
public static int binaryMin(int[] arr, int left, int right) {
//判斷0位置是不是區域最小
if (arr[0] < arr[1])
return 0;
//判斷arr.length-1位置是不是區域最小
if (arr[arr.length - 2] > arr[arr.length - 1])
return arr.length - 1;
if (left > right)//遞回結束
return -1;
int mid = (left + right) / 2;
int midVal = arr[mid];
//如果二分中點是區域最小
if (mid - 1 >= 0 && mid + 1 <= arr.length - 1 && midVal < arr[mid - 1] && midVal < arr[mid + 1])
return mid;
//如果二分中點大于等于左邊元素,向左遞回
else if (mid - 1 >= 0 && mid + 1 <= arr.length - 1 && midVal >= arr[mid - 1])
return binaryMin(arr, left, mid - 1);
//向右遞回
else
return binaryMin(arr, mid + 1, right);
}
由此可見，不是只有陣列有序才能二分，無序也可以，取決于特殊的問題和資料狀況
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/287731.html
標籤：其他
上一篇：【期末復習】?考試月來臨！C語言復習，這一篇帶你逃離掛科區！（完結）
下一篇：嵌入式面試總結(持續更新)