Preview lessons, content and tests

Computer Science & Programming solved. All in one platform.

1. To trial the platform and take tests, please take a few seconds to SIGN UP and SET UP FREE.
2. Searching for something specific? See our text overview of all tests. Scroll right for levels, and lists.

Student and Teacher User Guides |   Schemes of Work |   Real Teacher use Videos |

Join 30000+ teachers and students using TTIO.

Level

IB (Comp Sci)

Topic

04 - b - Algorithms

Binary Search

A binary search algorithm takes the data and keeps dividing it in half until it finds the item it is looking for.

Suggested Video

How to code a Binary search - step by step

A step by step explanation of how to code a Binary search in python using a relevant example: searching a friend list (e.g. facebook) for a friend!

Challenge

#1 Write a Python program to search using the binary search method

#2 Comment each line of the python solution below to show your understanding of the algorithm

Try it yourself

Solution

def binary_search(item_list,item):
	first = 0
	last = len(item_list)-1
	found = False
	while( first<=last and not found):
		mid = (first + last)//2
		if item_list[mid] == item :
			found = True
		else:
			if item < item_list[mid]:
				last = mid - 1
			else:
				first = mid + 1	
	return found
	
print(binary_search([1,2,3,5,8], 6))
print(binary_search([1,2,3,5,8], 5))

Explanation with Example


Imagine that you have a database 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. (Source: BBC Bitesize)


Above example represented as a flow chart 

A flowchart searching for a specific customer using binary search will find the midpoint of a list and discard the half of the list it doesn't need until it returns the correct customer's address.

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

General Flow Chart

Flowchart: Python Data Structures and Algorithms: Binary search

www.teachyourselfpython.com