詳解Java中二分法的基本思路和實(shí)現(xiàn)
在一個(gè)有序數(shù)組中，找某個(gè)數(shù)是否存在
思路：
- 由于是有序數(shù)組，可以先得到中點(diǎn)位置，中點(diǎn)可以把數(shù)組分為左右半邊。
- 如果中點(diǎn)位置的值等于目標(biāo)值，直接返回中點(diǎn)位置。
- 如果中點(diǎn)位置的值小于目標(biāo)值，則去數(shù)組中點(diǎn)左側(cè)按同樣的方式尋找。
- 如果中點(diǎn)位置的值大于目標(biāo)值，則取數(shù)組中點(diǎn)右側(cè)按同樣的方式尋找。
- 如果最后沒有找到，則返回：-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;
}
}
時(shí)間復(fù)雜度 O(logN)。
在一個(gè)有序數(shù)組中，找大于等于某個(gè)數(shù)最左側(cè)的位置
示例 1:
輸入: nums = [1,3,5,6], target = 5
輸出: 2
說明：如果要在num這個(gè)數(shù)組中插入 5 這個(gè)元素，應(yīng)該是插入在元素 3 和 元素 5 之間的位置，即 2 號(hào)位置。
示例 2:
輸入: nums = [1,3,5,6], target = 2
輸出: 1
說明：如果要在num這個(gè)數(shù)組中插入 2 這個(gè)元素，應(yīng)該是插入在元素 1 和 元素 3 之間的位置，即 1 號(hào)位置。
示例 3:
輸入: nums = [1,3,5,6], target = 7
輸出: 4
說明：如果要在num這個(gè)數(shù)組中插入 7 這個(gè)元素，應(yīng)該是插入在數(shù)組末尾，即 4 號(hào)位置。
通過上述示例可以知道，這題本質(zhì)上就是求在一個(gè)有序數(shù)組中，找大于等于某個(gè)數(shù)最左側(cè)的位置，如果不存在，就返回?cái)?shù)組長度（表示插入在最末尾位置）
我們只需要在上例基礎(chǔ)上進(jìn)行簡單改動(dòng)即可，上例中，我們找到滿足條件的位置就直接return了
if (arr[m] == t) {
return m;
}
在本問題中，因?yàn)橐业阶钭髠?cè)的位置，所以，在遇到相等的時(shí)候，只需要先把位置記錄下來，不用直接返回，然后繼續(xù)去左側(cè)找是否還有滿足條件的更左邊的位置。
同時(shí)，在遇到arr[m] > t條件下，也需要記錄下此時(shí)的m位置，因?yàn)檫@也可能是滿足條件的位置。
代碼：
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;
}
}
整個(gè)算法的時(shí)間復(fù)雜度是O(logN)。
在排序數(shù)組中查找元素的第一個(gè)和最后一個(gè)位置
思路
本題也是用二分來解，當(dāng)通過二分找到某個(gè)元素的時(shí)候，不急著返回，而是繼續(xù)往左（右）找，看能否找到更左（右）位置匹配的值。
代碼如下：
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;
}
}
時(shí)間復(fù)雜度 O(logN)。
局部最大值問題
思路
假設(shè)數(shù)組長度為N，首先判斷0號(hào)位置的數(shù)和N-1位置的數(shù)是不是峰值位置。
0號(hào)位置只需要和1號(hào)位置比較，如果0號(hào)位置大，0號(hào)位置就是峰值位置，可以直接返回。
N-1號(hào)位置只需要和N-2號(hào)位置比較，如果N-1號(hào)位置大，N-1號(hào)位置就是峰值位置，可以直接返回。
如果0號(hào)位置和N-1在上輪比較中均是最小值，那么數(shù)組的樣子必然是如下情況：
由上圖可知，[0..1]區(qū)間內(nèi)是增長趨勢, [N-2...N-1]區(qū)間內(nèi)是下降趨勢。
那么峰值位置必在[1...N-2]之間出現(xiàn)。
此時(shí)可以通過二分來找峰值位置，先來到中點(diǎn)位置，假設(shè)為mid，如果中點(diǎn)位置的值比左右兩邊的值都大:
arr[mid] > arr[mid+1] && arr[mid] > arr[mid-1]
則mid位置即峰值位置，直接返回。
否則，有如下兩種情況：
情況一：mid 位置的值比 mid - 1 位置的值小
趨勢如下圖：
則在[1...(mid-1)]區(qū)間內(nèi)繼續(xù)二分。
情況二：mid 位置的值比 mid + 1 位置的值小
趨勢是：
則在[(mid+1)...(N-2)]區(qū)間內(nèi)繼續(xù)上述二分。
完整代碼
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;
}
}
時(shí)間復(fù)雜度O(logN)。
到此這篇關(guān)于詳解Java中二分法的基本思路和實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)Java二分法內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
Springboot使用JustAuth實(shí)現(xiàn)各種第三方登陸
本文主要介紹了Springboot使用JustAuth實(shí)現(xiàn)各種第三方登陸，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-07-07
基于SpringBoot實(shí)現(xiàn)IP黑白名單的詳細(xì)步驟
IP黑白名單是網(wǎng)絡(luò)安全管理中常見的策略工具,用于控制網(wǎng)絡(luò)訪問權(quán)限,根據(jù)業(yè)務(wù)場景的不同,其應(yīng)用范圍廣泛,比如比較容易被盜刷的短信接口、文件接口,都需要添加IP黑白名單加以限制,所以本文給大家介紹了基于SpringBoot實(shí)現(xiàn)IP黑白名單的詳細(xì)步驟,需要的朋友可以參考下2024-01-01
idea中使用Inputstream流導(dǎo)致中文亂碼解決方法
很多朋友遇到一個(gè)措手不及的問題當(dāng)idea中使用Inputstream流導(dǎo)致中文亂碼及Java FileInputStream讀中文亂碼問題，針對(duì)這兩個(gè)問題很多朋友不知道該如何解決，下面小編把解決方案分享給大家供大家參考2021-05-05
Java同樣也提供了拋出異常、捕捉異常和finally語句的使用來處理程序異常,下面就來具體看一下Java中的異常處理用法及其架構(gòu)和使用建議:2016-06-06
Java線程池ThreadPoolExecutor的使用及其原理詳細(xì)解讀
這篇文章主要介紹了Java線程池ThreadPoolExecutor的使用及其原理詳細(xì)解讀,線程池是一種多線程處理形式,處理過程中將任務(wù)添加到隊(duì)列,然后在創(chuàng)建線程后自動(dòng)啟動(dòng)這些任務(wù),線程池線程都是后臺(tái)線程,需要的朋友可以參考下2023-12-12
Java如何使用Set接口存儲(chǔ)沒有重復(fù)元素的數(shù)組
Set是一個(gè)繼承于Collection的接口，即Set也是集合中的一種。Set是沒有重復(fù)元素的集合，本篇我們就用它存儲(chǔ)一個(gè)沒有重復(fù)元素的數(shù)組2022-04-04
這篇文章主要介紹了@RequestBody獲取不到參數(shù)的問題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2023-11-11
這篇文章主要給大家介紹了關(guān)于java跳出for循環(huán)的三種常見方法,需要的朋友可以參考下2023-07-07
Java?中向?Arraylist?添加對(duì)象的示例代碼
本文介紹了如何在 Java 中向 ArrayList 添加對(duì)象，并提供了示例和注意事項(xiàng)，通過掌握這些知識(shí)，讀者可以在自己的 Java 項(xiàng)目中有效地使用 ArrayList 來存儲(chǔ)和操作對(duì)象,需要的朋友可以參考下2023-11-11
這篇文章主要為大家詳細(xì)介紹了java實(shí)現(xiàn)字符串反轉(zhuǎn)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2017-05-05