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

Question

I am trying to solve the LeetCode problem Find First and Last Position of Element in Sorted Array:

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

You must write an algorithm with O(log n) runtime complexity.

I am writing this code:

var searchRange = function(nums, target) {
  nums = nums.sort((a, b) => (a-b))
  let result = [];
  for(let i = 0; i < nums.length; i++) {
    if (nums[i] == target) {
      result.push(i)
    } else {
     result = [-1, -1]
    }
  }

  return result
};
 
console.log(searchRange([5,7,7,8,8,10], 8));

It should return:

[3, 4]

but it returns:

[-1, -1]

What is wrong?

标签： javascriptarrayssorting

Answer 1

Your else code is wiping out results from the previous iteration of the loop.

However, your code is not efficient:

First, it calls sort on an array that is given to be already sorted: so leave that out.

Secondly, as your code is visiting every element in the array, you still get a time complexity of O(n), not O(logn).

To get O(logn) you should implement a binary search, and then perform a search to find the start of the range, and another to find the end of it.

Here is how that could work:

function binarySearch(nums, target) {
    let low = 0;
    let high = nums.length;
    
    while (low < high) {
        let mid = (low + high) >> 1; // half way
        if (nums[mid] > target) {
            high = mid;
        } else {
            low = mid + 1;
        }
    }
    return high; // first index AFTER target
}

function searchRange(nums, target) {
    let end = binarySearch(nums, target);
    let start = binarySearch(nums, target - 1);
    return start === end ? [-1, -1] : [start, end - 1];
}
 
console.log(searchRange([5,7,7,8,8,10], 8));