Searching Algorithms in Javascript
Searching algorithms are used to find a specific element in an array, string, linked list, or some other data structure.
The most common search algorithms are:
In the Linear searching algorithm, we check for the element iteratively one by one from start to end to the other.
Linear search
How Linear Search Works?
- Step 1: First, read the array’s search element (Target element).
- Step 2: Set an integer i = 0 and repeat steps 3 to 4 until i reaches the array’s end.
- Step 3: Match the key with arr[i].
- Step 4: If the key matches, return the index. Otherwise, increment i by 1.
Below is the implementation of Linear Search in javascript:
Javascript
// Javascript code to linearly search x in arr[]. // If x is present then return its location, // otherwise return -1 function linearSearch(arr, n, x) { let i; for (i = 0; i < n; i++) if (arr[i] == x) return i; return -1; } // Function to call Linear Search method function searchInArr(arr, n, x) { // Function call let result = linearSearch(arr, n, x); if (result == -1) console.log("Element is not present in array"); else console.log("Element is present at index " + result); } // Driver code let arr = [10, 30, 50, 60, 70]; let n = arr.length; let x1 = 50; searchInArr(arr, n, x1); let x2 = 5; searchInArr(arr, n, x2); |
Element is present at index 2 Element is not present in array
Complexity Analysis of Linear Search Algorithm
- Time Complexity of Linear Search: O(N), where N is the number of elements in the Array
- Auxiliary Space Complexity of Linear Search: O(1)
- In this type of searching algorithm, we break the data structure into two equal parts and try to decide in which half we need to find the element target element.
Binary Search
How does Binary Search work?
To understand the working of binary search, consider the following illustration:
- First Step:
- Initially, the search space is from 0 to 9.
- Let’s denote the boundary by L and H where L = 0 and H = 9 initially.
- Now mid of this search space is M = 4.
- So compare the target with arr[M].
- Second Step:
- As arr[4] is less than the target, switch the search space to the right of 16, i.e., [5, 9].
- Now L = 5, H = 9, and M becomes 7.
- Compare target with arr[M].
- Third Step:
- arr[7] is greater than the target.
- Shift the search space to the left of M, i.e., [5, 6].
- So, now L = 5, H = 6 and M = 6.
- Compare arr[M] with the target.
- Here arr[M] and target are the same.
- So, we have found the target.
Here is the implementation of the above approach:
Javascript
// Iterative function to implement Binary Search let iterativeFunction = function (arr, x) { let start=0, end=arr.length-1; // Iterate while start not meets end while (start<=end){ // Find the mid index let mid=Math.floor((start + end)/2); // If element is present at mid, return True if (arr[mid]===x) return true; // Else look in left or right half accordingly else if (arr[mid] < x) start = mid + 1; else end = mid - 1; } return false; } // Driver code let arr = [1, 3, 5, 7, 8, 9]; let x = 5; if (iterativeFunction(arr, x, 0, arr.length-1)) console.log("Element found!"); else console.log("Element not found!"); x = 6; if (iterativeFunction(arr, x, 0, arr.length-1)) console.log("Element found!"); else console.log("Element not found!"); |
Element found! Element not found!
Time Complexity: O(logN)
Auxiliary Space: O(1)
Learn Algorithms with Javascript | DSA using JavaScript Tutorial
This Algorithms with Javascript tutorial is designed to help you understand and implement fundamental algorithms using the versatile JavaScript programming language. Whether you are a beginner in programming or looking to enhance your algorithmic skills, this guide will walk you through essential concepts, algorithms, and their implementations.
Table of Content
- What is an Algorithm?
- How to Start learning Algorithms in JavaScript?
- Must know Algorithms in DSA using JavaScript Tutorial
- Searching Algorithms in Javascript
- Sorting Algorithm in javascript
- Recursive Algorithm in javascript
- Backtracking Algorithm in javascript
- Dynamic Programming in javascript
- Mathematical Algorithms in javascript
- Bitwise Algorithms in javascript
- Frequently Asked Questions (FAQs) – DSA using JavaScript Tutorial