[LeetCode] 34. Find First and Last Position of Element in Sorted Array

轉自LeetCode

Given a sorted array of integers, find the starting and ending position of a given target value.

Your algorithm's runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

<Solution>

看到搜尋，又看到時間要求是 O(logn)

直覺就想到 binary search

但題目是要求 range

最直覺的作法就是 binary search 找到 target，然後再往兩邊找起始和結尾

可是這樣就不是 O(logn) 了，例如 [2,2,2,2,2] 找 2 的時候，往兩邊找的動作就是 O(n)

雖然還是會過，但是不符合題意

查了下資料，可以看這邊的說明

主要想法是

• 先找二分法找左邊界

• 如果沒有左邊界，就直接結束

• 再找右邊界

實作上有幾個細節的部分要注意，可以上面提到的參考資料

code 如下

c++

kotlin