Leetcode 34. Find First and Last Position of Element in Sorted Array

[medium]

Find First and Last Position of Element in Sorted Array - LeetCode

[First — Gary brute force]

TC — O(n)

1. create an result array, assign the default result
2. scan through the array and put the first and last target number in the result.

[Second- binary Search Java]

test points

1. know how to use binary search to let the time complexity to O(log n)
2. trick part in binary search, know how to twist “mid” to make sure it won’t stuck in same number

[Think]

1. first, I want to find the most left target. So I will be no mercy on right number, if the mid number equal to target, I will keep pushing it. On the other hand, if the start pointer find the target, it will keep adding until the end.
2. using different color dots to image the target and mid number.
3. if it’s hard to imagine, try iterate example.