Introduction

Working Procedure

Do refer the code available the end of this section to understand the following theory.

1. Consider an array of n elements which are sorted in ascending order.
2. Create variables namely: low = 0, high = n-1, mid and pos = -1(Index of the element, if founded).
3. Loop if low < high
   1. Find the mid value, mid = (low + high) / 2.
   2. Check the array value at mid index with the element to be searched.
   3. If it matches then assign the mid+1 value to pos variable and break the loop.
   4. Else if array value at mid index is lesser than the element to be searched, then assign low = mid + 1. This will make the algorithm to search in second half(every time) there by reducing the time complexity.
   5. Else, assign high = mid - 1(eventually array value at mid index will be greater than the element to be searched). This will make the algorithm to search in first half(every time) there by reducing the time complexity.
4. After looping, if pos value is still -1 then it means that the element is not found in the given array.
5. If it's not -1 then element is found the position whose value is pos.

Time Complexity

PS: We give random inputs because the no. of input will generally be 100 or 1000 to find the time complexity and manually giving so many inputs is cumbersome work.

The basic operation in this algorithm is the comparision between each array element and the element to be searched(step 4.2 in the above working procedure). So increment the count variable above this if condition to get the count of no. of times the basic operation has been performed.

Time Complexity: O(logn)