Binary search operation in Javascript

We have an array of n elements. And, suppose we want to search some value x inside it. The first approach is having the linear search over it. But, for this the time complexity will be O(n).

If we want to reduce the time complexity, then we can go for Binary search.The different time complexities in different scenarios are :

a)Best Time complexity : O(1)

b)Average Time complexity is : O(log n)

c)Worst Time Complexity is : O(log n)

How The binary search algorithm works ?

So, in this approach , we first take the start index as 0. Again, we take the last index as Array.length-1 . Then we find the mid index using below formula

mid = (start+end)/2

a)If suppose the array value at  mid index that we just  calculated, is equal to the searchjElement then the search is over.

if(arr[mid]== searchElement)

b)If searchElement is smaller then mid index value. if(searchElement < arr[mid]).

then , again we have to search in first half of the array list

end = mid-1

c)If searchElement is greater then the mid index value, then we will start search in another right half of the array list

if(searchElement > arra[mid]){

start = mid+1;

}

Simple programme for binary search

Programme :

 

Find repeating element in the sorted array

By Pankaj Kumar Agarwal

 

 

 

 

 

 

 

 

 

 

Leave a reply:

Your email address will not be published.