AI solution for JavaScript Coding Question on BFE.dev
48. search first index with Binary Search(possible duplicate array)

Solution:

We can modify the binary search algorithm slightly to take care of duplicates. Instead of returning the index immediately when we find the target, we check if the previous element is equal to the target as well. If it is, we continue searching towards the left of the array. If it isn't, we return the current index.

Here's the JavaScript code:

/**
 * @param {number[]} nums - sorted ascending array with duplicates
 * @param {number} target
 * @return {number} - first index of target or -1 if not found
 */
function searchFirstIndex(nums, target) {
  let left = 0;
  let right = nums.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);

    if (nums[mid] === target) {
      // check if previous element is also target
      if (mid === 0 || nums[mid - 1] !== target) {
        return mid;
      } else {
        // continue searching towards left
        right = mid - 1;
      }
    } else if (nums[mid] > target) {
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }

  return -1;
}

Time Complexity: O(log N) where N is the length of the array.

Space Complexity: O(1).