Leetcode 162. Find Peak Element Binary search

A peak element is an element that is strictly greater than its neighbors.

Given a 0-indexed integer array nums, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks.

You may imagine that nums[-1] = nums[n] = -∞. In other words, an element is always considered to be strictly greater than a neighbor that is outside the array.

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

給予一個有多波的陣列,找出其中一個波頂的index並回傳。需使用O(log n)

可以想像陣列最外圍都是超級小的值,也就是說兩個極端邊的兩邊都會大於額外的element。

解題步驟

  1. 設定left 跟 right
  2. 假設n = 1 ,則直接回傳0
  3. 假設n = 2,則判斷大小回傳相對大的index
  4. 判斷頭尾,假設nums[0] > nums[1],則回傳0。假設nums[length-1] > nums[length-2],則回傳length-1
  5. while迴圈跑二分法
  6. 尋找mid,如果mid大於左右兩邊則回傳mid
  7. 如果mid > mid + 1 或 mid < mid – 1(edge case),則right = mid + 1
  8. 其他則設定left = mid – 1

Leave a Comment

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