How to use Binary Search In Javascript

Q: How to use Binary Search In Javascript

This method is similar to the above, the only difference is we will iterate the array in reverse order i.e. from last index to first.

Method 2: Using Linear Search (Reverse order)

Method 4: Using array.lastIndexOf() method

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 last occurrence in the right half again and provide the reuired output.

Example: In this example, we will use binary search to get the desired output.

Javascript

// 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; 
        left = 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( 
        "Last index of " + target + " is at index: " + outputIndex 
    ); 
}

Output

Last index of 5 is at index: 6

JavaScript Program to find the Index of Last Occurrence of Target Element in Sorted Array

In this article, we will see the JavaScript program to get the last occurrence of a number in a sorted array. We have the following methods to get the last occurrence of a given number in the sorted array.