Coding Challenge Practice - Question 40

The task is to implement binary search given a sorted array of ascending numbers, which might have duplicates, to return the first index of a target number.

The boilerplate code:

function firstIndex(arr, target){
  // your code here
}

The left is the first index of the array, the right is the second index of the array.

let left = 0;
let right = arr.length - 1
let result = -1

Find the middle of the array

let mid = Math.floor((left + right) / 2)

If the target is found arr[mid] === target, the value is stored in result, and the search is continued to the left to see if there's an earlier duplicate.

if(arr[mid] === target) {
result = mid;
right = mid - 1
}

If the middle value is smaller than the target, the search is continued to the right

else if (arr[mid] < target) {
left = mid + 1
}

If it is larger, the search is continued to the right.

else {
right = mid - 1
}

The final code

function firstIndex(arr, target){
  // your code here
  let left = 0;
  let right = arr.length - 1;
  let result =  -1;

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

    if(arr[mid] === target) {
      result = mid;
      right = mid - 1;
    } else if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return result;
}

That's all folks!