Skip to content

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

https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/

js
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var searchRange = function(nums, target) {
  return search(nums, target, 0, nums.length - 1)
}

function search(nums, target, l, r) {
  if (l > r) {
    return [-1, -1]
  }

  var m = (l + r) / 2 >> 0

  if (nums[m] < target) {
    return search(nums, target, m + 1, r)
  } else if (nums[m] > target) {
    return search(nums, target, l, m - 1)
  } else {
    let left = search(nums, target, l, m - 1)
    let right = search(nums, target, m + 1, r)

    return [
      left[0] === -1 ? m : left[0],
      right[1] === -1 ? m : right[1]
    ]
  }
}
py
class Solution(object):

    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        return self.search(nums, target, 0, len(nums) - 1)

    def search(self, nums, target, l, r):
        if l > r:
            return [-1, -1]
        m = (l + r) // 2
        if nums[m] < target:
            return self.search(nums, target, m + 1, r)
        elif nums[m] > target:
            return self.search(nums, target, l, m - 1)
        else:
            left = self.search(nums, target, l, m - 1)
            right = self.search(nums, target, m + 1, r)
            return [
                m if left[0] == -1 else left[0],
                m if right[1] == -1 else right[1]
            ]