本篇文章為大家帶來了關於java的相關知識，二分法是一個非常有效率的演算法，它常常用於電腦的查找過程。以下將透過範例為大家詳細講二分法的基本想法和實現，希望對大家有幫助。
推薦學習：《java影片教學》
在有序數組中，找某個數是否存在
想法：
- 由於是有序數組，可以先得到中點位置，中點可以把數組分成左右半邊。
- 如果中點位置的值等於目標值，直接傳回中點位置。
- 如果中點位置的值小於目標值，則去數組中點左側以相同的方式尋找。
- 如果中點位置的值大於目標值，則取數組中點右側以相同的方式尋找。
- 如果最後沒有找到，則回傳：-1。
程式碼
class Solution {
public int search(int[] arr, int t) {
if (arr == null || arr.length < 1) {
return -1;
}
int l = 0;
int r = arr.length - 1;
while (l <= r) {
int m = l + ((r - l) >> 1);
if (arr[m] == t) {
return m;
} else if (arr[m] > t) {
r = m - 1;
} else {
l = m + 1;
}
}
return -1;
}
}登入後複製
時間複雜度 O(logN)。
在一個有序數組中，找大於等於某個數最左邊的位置
#範例1:
##輸入: nums = [1,3,5,6], target = 5
輸出: 2
說明：如果要在
num這個陣列中插入5 這個元素，應該是插入在元素3 和元素5 之間的位置，即2 號位置。
範例 2:
輸入: nums = [1,3,5,6], target = 2
輸出: 1
##說明：如果要在
num
這個陣列中插入2 這個元素，應該是插入在元素1 和元素3 之間的位置，也就是1 號位置。
輸入: nums = [1,3,5,6], target = 7
輸出: 4
說明：如果要在
num
這個陣列中插入7 這個元素，應該是插入在陣列結尾，也就是4 號位置。
在一個有序數組中，找大於等於某個數最左邊的位置，如果不存在，就回傳數組長度（表示插入在最末尾位置）
我們只需要在上例基礎上進行簡單改動即可，上例中，我們找到滿足條件的位置就直接
return
#了<div class="code" style="position:relative; padding:0px; margin:0px;"><pre class="brush:java;">if (arr[m] == t) {
return m;
}</pre><div class="contentsignin">登入後複製</div></div>在這個問題中，因為要找到最左邊的位置，所以，在
遇到相等的時候，只需要先把位置記錄下來，不用直接返回，然後繼續去左側找是否還有滿足條件的更左邊的位置。
同時，在遇到
arr[m] > t
條件下，也需要記錄下此時的m位置，因為這也可能是滿足條件的位置。
class Solution {
public static int searchInsert(int[] arr, int t) {
int ans = arr.length;
int l = 0;
int r = arr.length - 1;
while (l <= r) {
int m = l + ((r - l)>>1);
if (arr[m] >= t) {
ans = m;
r = m - 1;
} else {
l = m + 1;
}
}
return ans;
}
}登入後複製
整個演算法的時間複雜度是
O(logN)
。
#思路
本題也是用二分來解，當透過二分找到某個元素的時候，不急著返回，而是繼續往左（右）找，看能否找到更左（右）位置匹配的值。
程式碼如下：
class Solution {
public static int[] searchRange(int[] arr, int t) {
if (arr == null || arr.length < 1) {
return new int[]{-1, -1};
}
return new int[]{left(arr,t),right(arr,t)};
}
public static int left(int[] arr, int t) {
if (arr == null || arr.length < 1) {
return -1;
}
int ans = -1;
int l = 0;
int r = arr.length - 1;
while (l <= r) {
int m = l + ((r - l) >> 1);
if (arr[m] == t) {
ans = m;
r = m - 1;
} else if (arr[m] < t) {
l = m +1;
} else {
// arr[m] > t
r = m - 1;
}
}
return ans;
}
public static int right(int[] arr, int t) {
if (arr == null || arr.length < 1) {
return -1;
}
int ans = -1;
int l = 0;
int r = arr.length - 1;
while (l <= r) {
int m = l + ((r - l) >> 1);
if (arr[m] == t) {
ans = m;
l = m + 1;
} else if (arr[m] < t) {
l = m +1;
} else {
// arr[m] > t
r = m - 1;
}
}
return ans;
}
}登入後複製
時間複雜度
O(logN)
。
想法
假設陣列長度為
N
，先判斷0 號位置的數和N-1位置的數是不是峰值位置。
0
號位置只需要和1號位置比較，如果0號位置大，0號位置就是峰值位置，可以直接返回。
N-1
號位置只需要和N-2號位置比較，如果N-1號碼位置大， N-1號位置就是峰值位置，可以直接回傳。
0
號位置和N-1在上輪比較中都是最小值，那麼陣列的樣子必然是如下情況：
由上圖可知，
[0..1]
區間內是成長趨勢, [N-2...N-1]區間內是下降趨勢。
[1...N-2]
之間出現。
二分
來找峰值位置，先來到中點位置，假設為mid，如果中點位置的值比左右兩邊的值都大:<div class="code" style="position:relative; padding:0px; margin:0px;"><pre class="brush:java;">arr[mid] > arr[mid+1] && arr[mid] > arr[mid-1]</pre><div class="contentsignin">登入後複製</div></div>則
mid
位置即峰值位置，直接回傳。
情況一：mid 位置的值比 mid - 1 位置的值小
趋势如下图：
则在[1...(mid-1)]区间内继续二分。
情况二：mid 位置的值比 mid + 1 位置的值小
趋势是：
则在[(mid+1)...(N-2)]区间内继续上述二分。
完整代码
public class LeetCode_0162_FindPeakElement {
public static int findPeakElement(int[] nums) {
if (nums.length == 1) {
return 0;
}
int l = 0;
int r = nums.length - 1;
if (nums[l] > nums[l + 1]) {
return l;
}
if (nums[r] > nums[r - 1]) {
return r;
}
l = l + 1;
r = r - 1;
while (l <= r) {
int mid = l + ((r - l) >> 1);
if (nums[mid] > nums[mid + 1] && nums[mid] > nums[mid - 1]) {
return mid;
}
if (nums[mid] < nums[mid + 1]) {
l = mid + 1;
} else if (nums[mid] < nums[mid - 1]) {
r = mid - 1;
}
}
return -1;
}
}登入後複製
时间复杂度O(logN)。
推荐学习：《java视频教程》
以上是簡單了解Java中二分法的基本想法與實現的詳細內容。更多資訊請關注PHP中文網其他相關文章！
