Coding Challenge Practice - Question 44

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

The boilerplate code:

function elementAfter(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 lastIndex = -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 right to see if there's a later duplicate.

if(arr[mid] === target) {
lastIndex = mid;
left= 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 (lastIndex === target) return undefined;

If the target is the last element, then there's nothing after it

if(lastIndex === arr.length - 1) return undefined

The result returned is the element just after the last element

return arr[lastIndex + 1]

The final code

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

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

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

  return arr[lastIndex + 1]
}

That's all folks!