Searching techniques in JavaScript

In today’s life of the software developer, JavaScript is the mandate for everyone. After coming of different frameworks in JavaScript like Node JS, Angular, React etc, it becomes more popular in the between of the software developers. But nowadays, JavaScript Developer wants to turn back to core programming.

So, I’ve started a series of core javascript programming, In which I have covered all the topics of javascript for beginners, intermediate and advanced developers.

Searching is very important in the day to day life of a programmer. If your file is too large and you want to find a specific word to be searched, so you need a search engine.

Types of Searching in Programming world :

There are two types of searching :

1. Linear Search ( Sequential Search )
2. Binary Search ( Half interval Search )

Linear Search :

In programming, linear search ( sequential search ) is the method of finding an item from an array or a list. It sequentially checks all the items of an array or list for the target value until a match is found or all the items have been searched.

Linear search

Elaboration of code:

1. In the first step, we create function taking two parameters namely arr and num
2. After that, we perform for loop on the array and compare each value of the array with num value.
3. If we found the searched item then it returns of the index value of searched item otherwise returns -1

Performance Analysis of linear search :

worst-case performance ---- O(n)
best-case performance ---- O(1)
average-case performance ---- O(n)
worst-case space complexity ---- O(1)

Binary Search :

Binary search is also known as Half interval search. In this type of search algorithm, we just break out the array from the midpoint. If the midpoint is equal to the target value,then it returns the index value of the searched item in the array. If mid value is less than the target value, then the value of Left is (mid+1) otherwise Right is (mid -1) and searched into sub-arrays. This searching is performed until the target value isfound or item is not available in the list.

An algorithm of Binary Search:

Given an array of A and having n no. of sorted items like A[0] <= A[1] <= A[2] <= .... <= A[n-1] <= A[n] and T is the target value. The below algo find the index of target value in A array.
1. Set Left = 0 and Right = n-1
2. If Left > Right, Binary Search terminates as unsuccessful
3. Set m (middle element) to the floor of (Left + Right)/2
4. If A[m] > T, then set Right to m-1 and go to step 2.
5. If A[m] < T, then set Left to m+1 and go to step 2.
6. If A[m] = T, search is done, return the value of m.

Functional transformation of the above algorithm :

function binary_search ( A, n, T ) :
  L = 0
  R = n - 1
  while R > = L
    m = floor((L+R)/2)
    If A[m] > T
      R = m-1
    Else if A[m] < T
      L = m+1
    Else
      return m
  return unsuccessful

Code snippet of binary search:

Binary Search

Elaboration of above code snippet :

1. In the first step, we create a function which has three parameters namely,arr arr.lengthnum
2. After that, we give the value toarr.length the variablen
3. In the next line, we perform the sorting in given arr array.

var sortedArr = arr.sort(function (a, b) {
     return a-b;  
});

4. After that assign the 0 to left and ton-1 right.

5. Now we just put the while loopwithleft <=right In the while loop, give the floor value of the sum of the left and right value then divide by 2 to mid variable(var mid = Math.floor((left+right)/2)) and we can check three conditions:

1. If the value of sortedArr[m] === num, then return the value of mid.
if(sortedArr[mid] === num) {
         return mid    
      }
2.If sortedArr[mid] > num, then right is mid -1
if (sortedArr[mid] > num) {
  right = mid - 1;
}
3. If sortedArr[mid] < num, then left is mid + 1
else {      
  left = mid + 1;    
}

6. If,left >right then the item to be searched is not present in the list or array.

Binary search by the recursive method :

Main difference of simple function of binary search and recursive method is that we call binary_search_recursive function in each if else condition.

1. If the value of sortedArr[m] === num, then return the value of mid.
if(sortedArr[mid] === num) {
         return mid    
      }
2.If sortedArr[mid] > num, then right is mid -1
if (sortedArr[mid] > num) {
  right = mid - 1;
  return binary_search_recursive(arr, left, right, num);
}
3. If sortedArr[mid] < num, then left is mid + 1
else {      
  left = mid + 1;   
  return binary_search_recursive(arr, left, right, num); 
}

Performance Analysis of Binary Search :

worst-case performance ---- O(log n)
best-case performance ---- O(1)
average-case performance ---- O(log n)
worst-case space complexity ---- O(1)

Conclusion :

This article covers the concept of linear search and binary search in the javascript. If you have any doubts and want to take any help from me please mail me to vsvaibhav2016@gmail.com. In the next topic we will cover the sorting techniques in Javascript.

Sorting techniques in JavaScript