Binary search
Binary search is a faster method for searching for an item that is in an ordered list.
An ordered list is one where the sequence of items in the list is important. An ordered list does not necessarily contain a sequence of numbers (eg 1, 2, 3, 4) or characters (eg A, B, C, D). It might also contain, eg a list of names in alphabetical order, a list of files from smallest to largest or a list of records from earliest to most recent.
Example
Imagine that you have a databaseA data store designed in an organised way, making it easier to search for the information you need. of customers and want to search for the customer John Smith. We first need the database to be ordered into alphabetical order by surname. We then search for the record ‘John Smith’ by surname.
The binary search will split the database in half, and compare the midpoint (the middle name) to the name ‘John Smith’. It will see whether the midpoint comes before or after ‘Smith’ and will throw away the set of records that doesn’t contain ‘Smith’ as a surname. It will keep dividing the records in that way until it reaches two records left, one of which is ‘John Smith’. It will then throw away the other record and output John Smith’s details. Binary search effectively divides the data in half and throws away, or ‘bins’ the half that does not contain the search term.
In pseudocode Also written as pseudo-code. A method of writing up a set of instructions for a computer program using plain English. This is a good way of planning a program before coding. this would look like:
OUTPUT "Which customer do you want to find?"
INPUT user inputs John Smith
STORE the user's input in the customer_name variable
customer_found = False
(we need to create a flag that identifies if the customer is found)
WHILE customer_found = False:
Find midpoint of list
IF customer_name = record at midpoint of list THEN
customer_found = True
ELSE IF customer comes before the midpoint THEN
throw away the second half of the list
ELSE
throw away the first part of the list
OUTPUT customer details
As a flowchartA diagram that shows a process, made up of boxes representing steps, decision, inputs and outputs., this would look like: