Find First and Last Position of Element in Sorted Array

Description

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]

 

Constraints:

• 0 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9
• nums is a non decreasing array.
• -10^9 <= target <= 10^9

Solution(javascript)

// const searchRange = (nums = [], target) => {
//   let left = 0
//   let right = nums.length - 1
//   let last = -1
//   let first = -1
//   let pivot = -1
//   while (left <= right) {
//     const middle = Math.floor((left + right) / 2)
//     if (nums[middle] === target) {
//       pivot = middle
//       break
//     } else if (nums[middle] < target) {
//       left = middle + 1
//     } else {
//       right = middle - 1
//     }
//   }
//   let temRight = pivot
//   while (left <= temRight) {
//     const middle = Math.floor((left + temRight) / 2)
//     if (nums[middle] === target) {
//       first = middle
//       temRight = middle - 1
//     } else if (nums[middle] < target) {
//       left = middle + 1
//     } else {
//       temRight = middle - 1
//     }
//   }
//   let temLeft = pivot
//   while (temLeft <= right) {
//     const middle = Math.floor((temLeft + right) / 2)
//     if (nums[middle] === target) {
//       last = middle
//       temLeft = middle + 1
//     } else if (nums[middle] < target) {
//       temLeft = middle + 1
//     } else {
//       right = middle - 1
//     }
//   }
//   return [first, last]
// }



const searchRange = (nums = [], target) => {
  const binarySearch = (left, right, position = 'middle') => {
    let pivot = -1
    while (left <= right) {
      const middle = Math.floor((left + right) / 2)
      if (nums[middle] === target) {
        if (position === 'middle') {
          pivot = middle
          break
        } else if (position === 'left') {
          pivot = middle
          right = middle - 1
        } else if (position === 'right') {
          pivot = middle
          left = middle + 1
        }
      } else if (nums[middle] < target) {
        left = middle + 1
      } else {
        right = middle - 1
      }
    }
    return pivot
  }


  const pivot = binarySearch(0, nums.length - 1, 'middle')
  return [
    binarySearch(0, pivot, 'left'),
    binarySearch(pivot, nums.length - 1, 'right'),
  ]
}