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!
