Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction 
2.
Linear Search
2.1.
Algorithm
2.2.
Time complexity 
3.
Binary Search
3.1.
Algorithm
3.2.
Time complexity 
4.
Implementation of Linear Search in Javascript
5.
Implementation of Binary Search in Javascript
5.1.
Recursive approach
5.2.
Iterative approach
6.
Frequently Asked Questions
7.
Conclusion
Last Updated: Mar 27, 2024
Easy

Implement Linear Search and Binary Search in an Array

Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction 

The most common task which usually is performed is searching. There are many algorithms to make the searching task efficient. Some of them are linear and binary searches which we will discuss in this blog.

We will first go through the concept of linear search and binary search. Furthermore, we will see linear and binary search implementation in javascript.

Linear Search

The linear search method is a fundamental search technique. A sequential search is performed on all things in this sort of search. Every item is verified, and if a match is discovered, that item is returned; if not, the search continues until the data collection is complete.

Algorithm

  • Starting with the leftmost member of arr[], compare x to each element of arr[] one by one.
  • Return the index if x matches an element.
  • Return -1 if x does not match any of the elements.

Time complexity 

  • The best-case complexity of the linear search is O(1) when the element is found at the first index. When the element is discovered at the last position or the element is not there in the array, the worst-case complexity is O(n).
  • The best-case complexity of the binary search is O(1) when the element is discovered at the middle index. The complexity in the worst-case scenario is O(log2n).
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Binary Search

The divide-and-conquer algorithm is used for binary search. We divide the array into halves in this algorithm and check whether the element we are searching for is in part or not by comparing the middle element value which the details value we are searching for in the array.

We need a sorted array for performing a binary search.

Binary search is substantially faster than linear search, with a Time Complexity of O(logN), whereas linear search has an O(N) time complexity.

Algorithm

  • Begin by creating an interval that spans the entire array.
  • If the search key's value is less than the item in the interval's midpoint, the interval should be narrowed to the lower half.
  • Otherwise, limit it to the upper half of the array.
  • Until the value is found or the interval is empty, check the value.

Time complexity 

The binary search algorithm has an O time complexity (log n). The best-case time complexity is O when the central index directly matches the required value (1). The values at either end of the list, or values not on the list, could constitute the worst-case situation.

Implementation of Linear Search in Javascript

function linearSearch(array, find_number) {
    for (let i = 0; i < array.length; i++) {
        if (array[i] === find_number) return "Element found!";
    }
    return "Element not found!";
}
var output = linearSearch([1, 3, 7, 3, 9], 8);
console.log(output);

 

Output-

Implementation of Binary Search in Javascript

Recursive approach

Recursion is a self-calling procedure. A recursive function is a function that calls itself. Recursive functions use the following syntax: function recurse() / function code recurse(); / function code recurse(); The recurse() method is a recursive function in this case.

Now, we will see the recursive approach for Binary search.

let recursiveFunction = function(arr, y, start, end) {

    if (start > end) return false;


    let mid = Math.floor((start + end) / 2);


    if (arr[mid] === y) return true;

    if (arr[mid] > y)
        return recursiveFunction(arr, y, start, mid - 1);
    else
        return recursiveFunction(arr, y, mid + 1, end);
}


let arr = [1, 3, 5, 7, 8, 9];
let find_number = 5;


if (recursiveFunction(arr, find_number, 0, arr.length - 1))
    document.write("Element found!");
else document.write("Element not found!");


find_number = 6;


if (recursiveFunction(arr, find_number, 0, arr.length - 1))
    document.write("Element found!");
else document.write("Element not found!");

Must Read Recursive Binary Search.

Output-

Iterative approach

Loops allow programs to do things like iterate through an array while adhering to the DRY principle (Don't Repeat Yourself). Now, we will see the iterative approach for Binary search.

const binarySearch = (array, target) => {
    if (array == null || array.length == 0)
        return -1;
    let left = 0;
    let right = array.length - 1;
    while (left <= right) {
        let middle = Math.floor((left + right) / 2);
        if (target === array[middle]) {
            return middle;
        } else if (target < array[middle]) {
            right = middle - 1;
        } else {
            left = middle + 1;
        }
    }
    return -1;
}
let array = [4, 6, 7, 32, 45, 98, 41, 23, 0];


let target = 32;


console.log(binarySearch(array, target));


target = 10;
console.log(binarySearch(array, target));

 

Output-


Must Read Fibonacci Series in JavaScript

Frequently Asked Questions

  1. What is linear search?
    The linear search method is a fundamental search technique. A sequential search is performed on all things in this sort of search. Every item is verified, and if a match is discovered, that item is returned; if not, the search continues until the data collection is complete.
     
  2. What is binary search?
    The divide-and-conquer algorithm is used for binary search. In this algorithm, we divide the array into halves and check whether the element we are searching for is in part or not by comparing the middle element value which the details value we are searching for in the array.
     
  3. Why do we use linear and binary search?
    If we want to search for an element in an array, we use searching methods like linear search and binary search, which use different algorithms to find the array's component.
     
  4. What is sorting?
    A sorting algorithm arranges the contents of a list in a specific order.
     
  5. What are the other searching algorithms?
    There are many searching algorithms, but some of them are -
    Jump Search
    Interpolation Search
    Sublist Search (Search a linked list in another list)
    Fibonacci Search
    Exponential Search
    The Ubiquitous Binary Search

Conclusion

In this article we have extensively discussed Implement Linear Search and Binary Search in an Array.

We hope that this blog has helped you enhance your knowledge regarding encryption and if you would like to learn more, check out our articles on Debounce and ThrottleFind the Second Highest Element in an Array and Sort an Array with and without inbuilt methods.

 

Recommended problems -

 

Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. Enrol in our courses and refer to the mock test and problems available. Take a look at the interview experiences and interview bundle for placement preparations.

Do upvote our blog to help other ninjas grow. 

Happy Learning!

Previous article
Fibonacci Series in JavaScript
Next article
Implement Flatten Method on an Array with and without Inbuilt Methods
Live masterclass