Algorithm - Searching - Binary Search - Problem Solving - Optimum Solution
In this article, we are covering most of the Binary Search based problem and respective optimum solutions.
Before we start let me explain Binary Search in detail.
Data structure and Algorithms Binary Search
Binary search is a fast search algorithm with run-time complexity of Ο(log n). This search algorithm works on the principle of divide and conquer. For this algorithm to work properly, the data collection should be in the sorted form.
The binary search looks for a particular item by comparing the middle most item of the collection. If a match occurs, then the index of the 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. This process continues on the sub-array as well until the size of the sub-array reduces to zero.
How Binary Search Works?
As depicted in below diagram,
For a binary search to work, it is mandatory for the target array to be sorted. We shall learn the process of binary search with a pictorial example. The following is our sorted array and let us assume that we need to search the location of value 14 using binary search.
First, we shall determine half of the array by using this formula,
int mid = (begin + end) / 2;
Then check if A[mid] is expected k, else check if it is less than 14, set the begin as mid+1 as per below logic,
if(A[mid]==k)
{
return mid;
}
else if(A[mid]>k)
{
end = mid - 1;
}
else
{
begin = mid + 1;
}
Then it will go for next iteration and recalculate the mid, and check for A[mid] ==k, now it is matching and we have resolved the problem.
Pseudocode
The pseudocode of binary search algorithms should look like this:
Procedure binary_search
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) / 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
end while
end procedure
Problems and Solutions
Here are few important examples of Binary Search based Algorithm problems:
Problem 1.1: Computing Square Root
Click here to download - Implement a fast Square root of an integer function
Problem 1.2: Search A sorted Array For k
Click here to download - Implement a fast Search A sorted Array For k function