Week 4
Binary search
Binary search is an efficient fundamental algorithm in computer science to find an element in the array. In binary search array have to be sorted. Main Principal in this algorithm is divide and conquer strategy. Watch the following video to see a sample.
To understand this algorithm follow the steps in the following example.
In below, sorted array we are looking for the location of the value 31.
In order to find the location of targeted value ‘31’ we have to find the middle of the array. You can find the middle of an array with the following formula.
mid = low + (high - low) / 2
So in our example will be like this:
0 + (9 - 0) / 2 = int (4.5) = 4
Mid = 4
After finding the mid index, we compare the value, which stored in the location mid to see is target search or not. List [4] = 27, and 27 is not our target search. As in binary search, we have a sorted array we know that our target ‘31’ is in the upper portion of the array not in lower portion. Let’s carry on, we need to change our ‘mid’ variable to ‘mid +1’ to check the upper portion of the array. low = mid + 1 mid = low + (high - low) / 2
Therefore, we limit our search area in just this portion, as we know our target search located in this portion.
In this portion our new mid is mid = low + (high - low) /2 = 7
Now again after determining the new mid we compare our target search ‘31’ with the value stored in mid. 31 ≠ 35 In this situation our target located in the lower portion, so new high is ‘high = mid -1 => 7 – 1 = 6’ mid is (high + low / 2=> 6 + 5 = 11/2 = 5
So 5 is the new mid here.
First, we have to compare the value of mid is equal to the target value as before. Value in mid ‘31’ = target value ‘31’
Algorithm conduct that target value is located at location 5.
Finally, we can type the bobble search in Pseudocode as below:
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
end while
These two videos help you to a better understanding that how binary search works.