Java二分法如何實現(xiàn)

本文小編為大家詳細介紹“Java二分法如何實現(xiàn)”，內(nèi)容詳細，步驟清晰，細節(jié)處理妥當，希望這篇“Java二分法如何實現(xiàn)”文章能幫助大家解決疑惑，下面跟著小編的思路慢慢深入，一起來學(xué)習(xí)新知識吧。

在一個有序數(shù)組中，找某個數(shù)是否存在

思路：

• 由于是有序數(shù)組，可以先得到中點位置，中點可以把數(shù)組分為左右半邊。

• 如果中點位置的值等于目標值，直接返回中點位置。

• 如果中點位置的值小于目標值，則去數(shù)組中點左側(cè)按同樣的方式尋找。

• 如果中點位置的值大于目標值，則取數(shù)組中點右側(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;
    }
}

時間復(fù)雜度 O(logN)。

在一個有序數(shù)組中，找大于等于某個數(shù)最左側(cè)的位置

示例 1:

輸入: nums = [1,3,5,6], target = 5

輸出: 2

說明：如果要在num這個數(shù)組中插入 5 這個元素，應(yīng)該是插入在元素 3 和 元素 5 之間的位置，即 2 號位置。

示例 2:

輸入: nums = [1,3,5,6], target = 2

輸出: 1

說明：如果要在num這個數(shù)組中插入 2 這個元素，應(yīng)該是插入在元素 1 和 元素 3 之間的位置，即 1 號位置。

示例 3:

輸入: nums = [1,3,5,6], target = 7

輸出: 4

說明：如果要在num這個數(shù)組中插入 7 這個元素，應(yīng)該是插入在數(shù)組末尾，即 4 號位置。

通過上述示例可以知道，這題本質(zhì)上就是求在一個有序數(shù)組中，找大于等于某個數(shù)最左側(cè)的位置，如果不存在，就返回數(shù)組長度（表示插入在最末尾位置）

我們只需要在上例基礎(chǔ)上進行簡單改動即可，上例中，我們找到滿足條件的位置就直接return了

if (arr[m] == t) {
    return m;
}

在本問題中，因為要找到最左側(cè)的位置，所以，在遇到相等的時候，只需要先把位置記錄下來，不用直接返回，然后繼續(xù)去左側(cè)找是否還有滿足條件的更左邊的位置。

同時，在遇到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;
    }
}

整個算法的時間復(fù)雜度是O(logN)。

在排序數(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;
    }
}

時間復(fù)雜度 O(logN)。

局部最大值問題

思路

假設(shè)數(shù)組長度為N，首先判斷0號位置的數(shù)和N-1位置的數(shù)是不是峰值位置。

0號位置只需要和1號位置比較，如果0號位置大，0號位置就是峰值位置，可以直接返回。

N-1號位置只需要和N-2號位置比較，如果N-1號位置大，N-1號位置就是峰值位置，可以直接返回。

如果0號位置和N-1在上輪比較中均是最小值，那么數(shù)組的樣子必然是如下情況：

由上圖可知，[0..1]區(qū)間內(nèi)是增長趨勢, [N-2...N-1]區(qū)間內(nèi)是下降趨勢。

那么峰值位置必在[1...N-2]之間出現(xiàn)。

此時可以通過二分來找峰值位置，先來到中點位置，假設(shè)為mid，如果中點位置的值比左右兩邊的值都大:

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;
    }
}

時間復(fù)雜度O(logN)。

讀到這里，這篇“Java二分法如何實現(xiàn)”文章已經(jīng)介紹完畢，想要掌握這篇文章的知識點還需要大家自己動手實踐使用過才能領(lǐng)會，如果想了解更多相關(guān)內(nèi)容的文章，歡迎關(guān)注億速云行業(yè)資訊頻道。