首頁 > Java > java教程 > 主體

簡單了解Java中二分法的基本想法與實現

WBOY
發布: 2022-08-25 11:35:55
轉載
1511 人瀏覽過

本篇文章為大家帶來了關於java的相關知識,二分法是一個非常有效率的演算法,它常常用於電腦的查找過程。以下將透過範例為大家詳細講二分法的基本想法和實現,希望對大家有幫助。

簡單了解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 號位置。 範例3:

輸入: 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] &gt; arr[mid+1] &amp;&amp; arr[mid] &gt; 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中文網其他相關文章!

相關標籤:
來源:jb51.net
本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
熱門教學
更多>
最新下載
更多>
網站特效
網站源碼
網站素材
前端模板