Coding Challenge Practice - Question 42

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

The boilerplate code:

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

if (arr[mid] === target) {
      result = 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
}

The final code

function lastIndex(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;
      left = mid + 1;
    } else if(arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return result;
}

That's all folks!