How to use Binary Search In Javascript
In this method, we will use Binary search to get the first occurance of target element. Binary search is an optimized technique which give output in O(log N) time. It works only for the sorted data. Using binary search if target element is found we will try to search the first occurrence in the left half again and provide the reuired output.
Example: In this example, we will use binary search to get the desired output.
// Input array
const arr = [1, 2, 3, 4, 5, 5, 5, 6, 6, 7, 8, 8, 9];
// Target element
const target = 5;
let left = 0;
let right = arr.length - 1;
let outputIndex = -1;
// Using binary search
while (left <= right) {
let mid = Math.floor((left + right) / 2);
// If found search left half for
// First occerrence
if (target === arr[mid]) {
// Store first occurrence index
outputIndex = mid;
right = mid - 1;
}
// If target is smallar discard right half
else if (target < arr[mid]) {
right = mid - 1;
}
// If target is greater discard left half
else
left = mid + 1;
}
// If not found display output
if (outputIndex === -1)
console.log(target + " is not present in the given");
else {
console.log(
"First index of " + target + " is: " + outputIndex
);
}
Output
First index of 5 is: 4
JavaScript Program to Find Index of First Occurrence of Target Element in Sorted Array
In this article, we will see the JavaScript program to get the first occurrence of a number in a sorted array. We have the following methods to get the first occurrence of a given number in the sorted array.