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 :

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
function binarySearch(arr,search){ var start = 0; var end = arr.length-1; for(start;start<end;){ var mid = parseInt((start+end)/2); if(arr[mid]==search){ return arr[mid]; } if(search<arr[mid]){ end = mid-1; } else{ start = mid+1; } } } var arr = [1,2,4,7,8,19,122]; var findElement = 19; var finalSearch = binarySearch(arr,findElement); console.log('The final search is ',finalSearch); |

Find repeating element in the sorted array

By Pankaj Kumar Agarwal