Implement Linear Search and Binary Search in an Array

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

You can also try this code with Online Javascript Compiler

Run Code

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!");

You can also try this code with Online Javascript Compiler

Run Code

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

You can also try this code with Online Javascript Compiler

Run Code

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 Throttle, Find the Second Highest Element in an Array and Sort an Array with and without inbuilt methods.

Recommended problems -

• Binary Array Sorting
• Vertical Order Traversal of a Binary Tree
• Leaf Nodes in Binary Tree
• Merge 2 Sorted Arrays

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!