- Binary search is a fast searching algorithm as compare to linear search algorithm.
- Binary search looks for a particular item by comparing the middle item with the searched value. If a match occurs, then the index of item is returned.
- If the middle item is greater than the item, then the item is searched in the sub-array to the left of the middle item. Otherwise, the item is searched for in the sub-array to the right of the middle item.
0 1 2 3 4 5 6 7
In the above array we have to search for an element 29.
Some terms related with binary search:-
Mid=( low + high )/2 = (0+7)/2 = 3.5 = (Approx) 3
The value present in index 3 is 21
Step1: we will compare the mid value 21 with the searched value 29.
29>21 so we will take the forward part of 21 and skip the other one.
3 4 5 6 7
Step 2: Again we have to calculate the low, high and mid value.
Mid=( low + high )/2= (4+7)/2 = 5.5 = (Approx) 5
The value present in index 5 is 29
We are searching for the value 29 and we got it.
So, the searched value 29 is present in the index value of 5.
A ← sorted array
n ← size of array
x ← value to be searched
Set lowerBound = 1
Set upperBound = n
while x not found
if upperBound < lowerBound
EXIT: x does not exists.
set midPoint = lowerBound + ( upperBound - lowerBound ) / 2
if A[midPoint] < x
set lowerBound = midPoint + 1
if A[midPoint] > x
set upperBound = midPoint - 1
if A[midPoint] = x
EXIT: x found at location midPoint
- Binary search is also known as “Half- Interval search”.
- Time complexity :
- Best case performance of binary search = O (1)
- Worst case performance of binary search = O (log n)
- Average case performance of binary search = O (log n)
Binary search algorithm is mostly used for making “Binary search tree” and “Hashing techniques”.
For performing binary search technique the array must be in sorted order. Binary search technique can’t be used in unsorted array.
But as compare to linear search , Binary search is preferable.