Binary Search
searching algorithms
Let's populate an array with random integers:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 |
Binary Search uses the value of the lower bound index of an array and the upper bound index to calculate the middle index.
If the item at the middle index is not the item being searched for it:
determines if the item being search for is less than the item at the middle index and updates the upper bound of the new search area to be middle - 1.
else it updates the lower bound of the new search area to be middle + 1.
This process continues until the item is found or the lower bound becomes equal to the upper bound.
Let's check out a simulation:
Here is another simulator now that you've got the hang of it!
Past Paper Questions
Tags
data type INTEGER pseudocode REAL program code DATE STRING CHAR bubble sort BOOLEAN declare variable
Let's say a global variable which is an array stores sorted values.
A function, BinarySearch, searches the array for an item.
If it finds the item, it returns it. Otherwise, it returns -1.
Complete the function below.
FUNCTION BinarySearch( arr : ARRAY[1:n] OF INTEGER, item : INTEGER) RETURNS INTEGER
lowerBound ←
← LENGTH(arr)
WHILE lowerBound <= upperBound DO
middle ← ()/2
IF arr[middle] = THEN
RETURN item
ELSE IF item < arr[middle] THEN
upperBound ←
ELSE
lowerBound ←
END IF
END WHILE
END FUNCTION
Code It!
To further your understanding of Binary Search, code the algorithm using your high-level langauge.
Test it by initialising a sorted array, calling the function with that array as a parameter, along with a search item.
Submit your solution as instructed.
RECURSION
We can recursively perform a binary search to return the index of the item we are searching for or -1 if the item is not found.
Note, we could also return the item or something to indicate that the item was not found...
To do this, we need to consider which variables are changing each time we make a recursive call. We can see that the lowerbound and upperbound are changing within the algorithm.
We also need to consider the base/end case.
Here is a function header for a recursive solution:
FUNCTION recursiveBinarySearch(arr:ARRAY OF INTEGER, item:INTEGER, lowerBound:INTEGER, upperBound:INTEGER) RETURNS INTEGER
Can you code and test a recursive version of Binary Search?