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

Problem:

Given an array of integers nums sorted in ascending order, 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].

 

Example 1:

Input: nums = [5,7,7,8,8,10], target = 8

Output: [3,4]

 

Example 2:

Input: nums = [5,7,7,8,8,10], target = 6

Output: [-1,-1]

 

-Summary-

Use binary search to solve a problem

1. Create a two helper function to find left-most and right-most index for a target number

2. In the 'findLeftIndex' function, we keep the search for the target number using binary search.

   - Unlike regular binary search, even though we found the target number in the middle of the index and exit. We keep the search on the list to find the left-most index and keep update if we found another Target number.

  - Same applies for the 'findRightIndex' function.

3. return with find index number range for left and right.

 

모든 문제에 대한 저작권은 LeetCode 회사에 있습니다. [Copyright © 2020 LeetCode]