SearchingBinary 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 database of customers and want to search for the customer "John Smith".

1. Before performing a binary search, the database must be sorted alphabetically by surname.
2. You can then search for the record "John Smith" using the surname.
3. The binary search starts at the midpoint of the list and compares the middle record with "John Smith".
4. If the midpoint record surname matches "John Smith", the search ends. If not, the search continues.
5. If the midpoint record comes alphabetically before "John Smith", the first half of the list is discarded, including the midpoint record.
6. If the midpoint record comes after "John Smith", the second half of the list is discarded, starting from the midpoint.

The search then repeats this process with the remaining records, finding the new midpoint each time. The search ends when either a match is found or there are no more records left to search through.

In pseudocode 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 flow diagram (also known as a flowchart,) this would look like: