Horje
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.

Methods to Find the Index of the First Occurrence of the element in the sorted array

Table of Content

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 first occurrence is matched.

Example: In this example. we will use linear search to get the first index 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 till length of array
for (let i = 0; i < arr.length; ++i) {

    // If target found return and exit program
    if (arr[i] === target) {
        console.log(
            "First index of " + target + " is: " + i
        );
        return;
    }
}

// If not found display output
console.log(target + " is not present in the given array");

Output
First index of 5 is: 4

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.

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;
        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

Method 3: Using array.indexOf() Method

In this approach, we will use array.indexOf() method. The JavaScript Array indexOf() Method is used to find the index of the first occurrence of the search element provided as the argument to the method. This method always compares the search element to the element present in the array using strict equality. Therefore, when the search element is not found then it returns -1 because NaN values are never compared as equal.

Syntax: 

array.indexOf(element, start)

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

JavaScript 
// Input array
const arr = [1, 2, 3, 4, 5, 5, 5, 6, 6, 7, 8, 8, 9];

// Target element
const target = 0;

// Get first index of element using 
// indexOf method()
const outputIndex = arr.indexOf(target);

// 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
0 is not present in the given

Method 4: Using array.findIndex() Method

In this approach, we will use Array.findIndex() method. The Javascript Array.findIndex() method is used to return the first index of the element in a given array that satisfies the provided testing function (passed in by the user while calling). Otherwise, if no data is found then the value of -1 is returned.

Syntax:

array.findIndex(function(currentValue, index, arr), thisValue)

Example: In this example, we will use arr.findIndex() method with a callback function as shown in the example to get desired output.

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
// findIndex() method
const outputIndex = arr.findIndex((e) => e === target);

// 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 8 is: 10

Method 5: Using Array.prototype.reduce() Method

In this approach, we will use the reduce() method to find the index of the first occurrence of the target element. The reducer function will check each element and return the index when the target is found for the first time. If the target is not found, it will return -1.

Example: In this example, we will use the reduce() method to find the target element.

JavaScript 
// Input array
const arr = [1, 2, 3, 4, 5, 5, 5, 6, 6, 7, 8, 8, 9];

// Target element
const target = 6;

// Use reduce() to find the first index of target element
const outputIndex = arr.reduce((acc, curr, index) => {
    // If accumulator is already found, return it
    if (acc !== -1) return acc;

    // If target found, return current index
    if (curr === target) return index;

    // Otherwise, keep searching
    return acc;
}, -1);

// If not found, display output
if (outputIndex === -1) {
    console.log(target + " is not present in the given array");
} else {
    console.log("First index of " + target + " is: " + outputIndex);
}

Output
First index of 6 is: 7




Reffered: https://www.geeksforgeeks.org

JavaScript

Related
JavaScript Program for Sum of Digits of a Number JavaScript Program for Sum of Digits of a Number
JavaScript Program to Print All Numbers Divisible by 3 and 5 of a Given Number JavaScript Program to Print All Numbers Divisible by 3 and 5 of a Given Number
JavaScript Program to Check if a number is Positive, Negative, or Zero JavaScript Program to Check if a number is Positive, Negative, or Zero
JavaScript Program to Check an Array is Sorted or Not JavaScript Program to Check an Array is Sorted or Not
JavaScript Program to Check if a String Contains any Special Character JavaScript Program to Check if a String Contains any Special Character

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



 

Horje