Leetcode 34. Find First and Last Position of Element in Sorted Array
Find First and Last Position of Element in Sorted Array - LeetCode
Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target…
[First — Gary brute force]
TC — O(n)
- create an result array, assign the default result
- scan through the array and put the first and last target number in the result.
[Second- binary Search Java]
- know how to use binary search to let the time complexity to O(log n)
- trick part in binary search, know how to twist “mid” to make sure it won’t stuck in same number
- 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.
- using different color dots to image the target and mid number.
- if it’s hard to imagine, try iterate example.