Binary search algorithm

In this article, We are going to learn binary search. Binary search is one of the searching algorithm only aplicable on sorted array.

Binary Search:-

If we have to perform searching in given array which is alreay sorted then binary search is efficent searching algorithm. works as follow

Binary Search Algorithm works as follows:-

During each stage of the binary search algorithm search space for search item is reduce to a segment of element. Array[low], Array[low+1], . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ., Array[high]. Here low and high denotes the beginning and the end location of search space.

In this algorithm we compare search item to the middle element of search space we can calculate mid index by mid=(low+high)/2

if Array[mid]=item than search is sucessfull and we found the search element in the array.

else we have to update the area of search space by updating value of low anad high.

if search item is less than Array[mid] then item can be found only in the first half of the search space. We have to update the value of high with mid-1 that is high = mid-1

if the search item is greater than Array[mid] then item can be found only in the second half of the search space. we have to update the value of low with mid+1 that is low=mid+1

Now search space is reduce we have to perform searching again.

Binary search algorithm:-

BinarySearch(array,search item)

Here array is a sorted array and the search item is given the information we have to search in the given array. We have to search in the array.

Steps:-

1. Initilize low with 0 and high with length of array-1. and mid=(low+high)/2.
2. Repeat Step 3 and 4 while low<=high and array[mid] not equal to i search item.
3. if search item<array[mid] then set high =mid-1 else set low = mid+1.
4. set mid=int(low+high)/2. End of step 2 loop.
5. if arrray[mid]=search item,then set search item is found at location mid. else not found.
6. exit

Time complexity of binary search:-

1. Time complexity of binary search in best case is O(1)..
2. Time complexity of binary search in average case is O(logn).
3. Time complexity of binary search in worst case is O(logn).