介紹另一種二分搜尋法的應用

題目連結: 162. Find Peak Element

題目描述:一個「峰值元素」是指其值嚴格大於其左右兩側相鄰元素的元素。給定一個 nums 陣列，其中 nums[i] != nums[i+1]，請找到任何一個峰值元素並返回其索引。你可以將 nums[-1] 和 nums[n] 想像為負無窮大 (-∞)。

注意:此題要求時間複雜度必須是 O(log n)。

Python

對於這題我當下的想法是陣列沒有排序，怎麼能用二分搜尋呢？

後來沉澱思考一下，明白二分搜尋的本質並不是「陣列必須排序」，而是「在每一步都能排除一半肯定沒有答案的區間」。

我們可以把這個陣列想像成一座山脈的海拔圖。

• 尋找峰值，就是在尋找任何一個山頂。

• 當我們站在山脈的任何一個點 mid，我們只需要抬頭看看旁邊，就能決定山頂在哪個方向：

  • 如果右邊的路是上坡 (nums[mid] < nums[mid+1])，那山頂必定在右邊。

  • 如果右邊的路是下坡 (nums[mid] > nums[mid+1])，那山頂必定在左邊（或者我們就站在山頂上）。

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        left = 0
        right = len(nums)-1
        while left<right:
            mid = (left+right)//2
            if nums[mid]>nums[mid+1]:
                right = mid
            else:
                left = mid + 1
        return right

演算法分析:

• 初始化 left 與 right。
• while迴圈的目的是不斷縮小搜索範圍。
• if nums[mid] > nums[mid+1]:知道目前位置比下一個位置還高，則我們可以直接捨棄右邊，right = mid，將搜索範圍縮小到[left, mid]。
• 最終，left 和 right 會在某個峰值點相遇。
• 我們每一步都朝著保證有峰值的方向移動，所以當 left == right 時，這個最後剩下的點必定是一個峰值。返回 right（left也一樣）即可。

複雜度分析:
* 每一次執行bs函式的時間複雜度都是 O(log n)，所以時間複雜度為 O(log n)。
* 空間複雜度為O(1)。

這樣有更了解二分搜尋的奧妙嘛!
今天就介紹到這邊，有問題都可以留言
下回見!!