Binary Search is a searching algorithm. It searches for an element in a sorted array in O(LogN).
In this article, we will discuss the principle behind Binary Search and the Pseudo code for recursive Binary Search.
First, assume that the array is sorted in Ascending order.
Binary Search is based on the principle that if an element X is smaller than array[i], then X is smaller than array[j] for all j >i.
Similarly, if an element X is greater than array[i] then X is greater than array[j] for all j < i.
Now, let’s talk about the case when array is sorted in descending order.
If X is smaller than array[i], then X is smaller than array[j] for all j < i.
Similarly, if X is greater than array[i], then X is also greater than array[j] for all j > i.
Recursive Binary Search Algorithm Pseudo code (Ascending Order)
array: array sorted in ascending order
start: first index of array
end: last index of array
x: search value
FUNCTION binary_search ( array , start , end , x )
WHILE start < end DO
mid := ( start + end ) / 2
IF x == array[mid] THEN
RETURN mid
ELSE IF x > array[mid] THEN
RETURN binary_search( array , mid + 1 , end , x )
ELSE
RETURN binary_search( array , start , mid - 1 , x )
END WHILE
END FUNCTION
Recursive Binary Search Algorithm Pseudo code (Descending Order)
array: array sorted in ascending order
start: first index of array
end: last index of array
x: search value
FUNCTION binary_search ( array , start , end , x )
WHILE start < end DO
mid := ( start + end ) / 2
IF x == array[mid] THEN
RETURN mid
ELSE IF x < array[mid] THEN
RETURN binary_search( array , mid + 1 , end , x )
ELSE
RETURN binary_search( array , start , mid - 1 , x )
END WHILE
END FUNCTION
What to Study next?
Leave Comment if You have Any Query
The code for ascending and descending order is the same.
It’s not the same. See carefully.