Coding Challenge Practice - Question 43

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

The boilerplate code:

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

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

let left = 0;
let right = arr.length - 1;
let firstIndex = -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 left.

else {
right = mid - 1
}

If not found, return undefined

if (firstIndex === target) return undefined;

If the target is the first element, then there's nothing before it

if(firstIndex === target) return undefined;

The final code

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

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

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

  if(firstIndex === 0) return undefined;

  return arr[firstIndex - 1];
}

That's all folks!