Binary Search
The next algorithm, we are going to study is Binary Search. As the name suggests, it is a searching algorithm. It is one of the very famous searching techniques. Unlike its counterpart linear search, it is way more advanced. Time complexity of linear search is O(N) whereas that of binary search is O (log N).
Source Code:
Output
Working
Let’s come
on to the working of the algorithm, as you can see in the above program, we
need a sorted array to perform binary search algorithm.
1. Here, bin function in the
above program it accepts 4 parameters, that is, the array arr, lower
index low, higher index high and the searching number sn.
2. Next, we have a do-while loop
to check if high is greater than or equal to low (high>=low).
If at any point of iteration this condition is not satisfied, it means the
searching number sn does not exist in the array.
Following is the algorithm for binary search:
while(high>=low)
{
mid= (low+high)/2;
/* mycodingnetwork.blogspot.com */
if(sn==a[mid])
return mid;
else if(sn>a[mid])
low=mid+1;
else if(sn<a[mid])
high=mid-1;
}
3. Inside the while loop, the mid
variable calculates the middle index of the array. The formula used for this is
(low+high)/2.
4. The mid variable is followed
by 3 conditional statements:
a. In the first conditional statement if
searching number is equal to middle index it returns mid as the answer.
b. In the second condition, if searching
number sn is greater than arr[mid], in this scenario low is
changed to mid+1, since it is obvious that the searching number does not
lie on the left side of the mid index.
c. In the third condition, if searching
number sn is lower than arr[mid], in this scenario high is
changed to mid-1, since it is obvious that the searching number does not
lie on the right side of the mid index.
The step 3 and 4 continues till high is greater than or equal to low, that is the condition of while loop, if this condition becomes false and no value is returned it means that the searching number does not exist in the given array therefore the exit the function will return -1.
Hope you liked this explanation, for any doubt or feedback you can comment down in the comment section.