Leetcode 153. Find Minimum in Rotated Sorted Array – Binary search

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:

  • [4,5,6,7,0,1,2] if it was rotated 4 times.
  • [0,1,2,4,5,6,7] if it was rotated 7 times.

Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Given the sorted rotated array nums of unique elements, return the minimum element of this array.

You must write an algorithm that runs in O(log n) time.

給定一個長度n的陣列,他會依照遞增排列,並且會被隨機旋轉1-n次。舉例來說:[0,1,2,4,5,6,7]可能會有以下結果

[4,5,6,7,0,1,2] 被旋轉4次
[0,1,2,4,5,6,7] 被旋轉7次

最終要用O(log n 完成)

思考步驟

  1. 為了找到最小值,要先取中間數,找出左右誰是有序的(有可能兩邊都有序)
  2. 假設兩邊都有序,直接回傳第一個
  3. 假設其中一邊有序,最小值必定在無序的那邊。
  4. 如果無序是在右邊,則每一次二分法找出mid < left的值回傳
  5. 如果無序是在左邊,則每一次二分法找出mid > right的值回傳
  6. 如果mid == left,則直接回傳right

Leave a Comment

發佈留言必須填寫的電子郵件地址不會公開。