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!
SOCIAL SHARE CARD GENERATOR