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

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.

Methods to Find the Index of the Last Occurrence of the Target Element in the Sorted Array

Using Linear Search(Brute Force method)
Using Linear Search (Reverse order)
Using binary search
Using array.lastIndexOf() method

Method 1: Using Linear Search

Linear search is a type of brute force method that works on linear traversal of the array. It searches the target in O(N) time. It works whether the array is sorted or not.

The program will run till the target is not found and will stop when the Last occurrence is matched.

Example: In this example. we will use linear search to get the last index of the target element.

Javascript

// Input sorted array 
arr = [1, 2, 3, 4, 5, 5, 5, 6, 6, 7, 8, 8, 9]; 
  
// Target element 
target = 5; 
  
// outputIndex 
let outputIndex = -1; 
  
// Iterate till length of array 
for (let i = 0; i < arr.length; ++i) { 
  if (arr[i] === target) outputIndex = i; 
  else if (arr[i] > target) break; 
} 
  
// If not found display output 
if (outputIndex === -1) 
  console.log(target + " is not present in the given"); 
else { 
  console.log( 
    "Last occurrence of " + 
    target + 
    " is at the index: " + 
    outputIndex 
  ); 
}

Output

Last occurrence of 5 is at the index: 6

Method 2: Using Linear Search (Reverse order)

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.

Example: In this method, we will use the reverse iteration in linear search to get the last occurance of target element.

Javascript

// Input array 
arr = [1, 2, 3, 4, 5, 5, 5, 6, 6, 7, 8, 8, 9]; 
  
// Target element 
target = 5; 
  
// Iterate from last to zero index 
for (let i = arr.length - 1; i >= 0; i--) { 
  
  // If target found return and exit program 
  if (arr[i] === target) { 
    console.log( 
      "The Last index of " + target + " is: " + i 
    ); 
    return; 
  } 
} 
  
// If not found display output 
console.log(target + " is not present in the given");

Output

The Last index of 5 is: 6

Method 3: Using Binary Search

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

Method 4: Using array.lastIndexOf() method

In this approach, we will use array.lastIndexOf() method. The JavaScript Array lastIndexOf() Method is used to find the index of the last occurrence of the search element provided as the argument to the function.

Syntax:

array.lastIndexOf(element, start)

Example: In this example, we will use arr.indexOf() method to find the last occurrence of target element

Javascript

// Input array 
const arr = [1, 2, 3, 4, 5, 5, 5, 6, 6, 7, 8, 8, 9]; 
  
// Target element 
const target = 8; 
  
// Get first index of element using indexOf method() 
const outputIndex = arr.lastIndexOf(target); 
  
// 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 8 is at index: 11

Elevate your coding journey with a Premium subscription. Benefit from ad-free learning, unlimited article summaries, an AI bot, access to 35+ courses, and more-available only with GeeksforGeeks Premium! Explore now!

Reffered: https://www.geeksforgeeks.org

JavaScript

Related
Applications of Recursion in JavaScript
JavaScript Program for Selection Sort
JavaScript Program for Insertion Sort
JavaScript Program for Merge Sort
JavaScript Program for Quick Sort

Type:	Geek
Category:	Coding
Sub Category:	Tutorial
Uploaded by:	Admin
Views:	10