By Monty, 27th April 2015

**Binary** **Search** is one of the most fundamental computer algorithms. Given an ordered list of some data (names, numbers, …) find out if it contains a particular item. For example, consider the list: 2, 4, 5, 7, 8, 11, 12. If we ask if it contains the number 5, the algorithm should return 2 (counting from 0). If we ask if it contains 9 the algorithm can return a value that can’t be a position, such as -1, to indicate the number wasn’t found. In practice, the list would comprise records containing the key, e.g. a name, and some associated data, e.g. a telephone number.

If you don’t know anything about how the keys are distributed, e.g. evenly, one good strategy would be to start your search in the middle. If you don’t find it immediately, compare it with the item in the middle – is it smaller or larger than that? If it’s larger, try looking in the middle of the top half of the list, other wise look in the middle of the bottom half of the list. This is a recursive procedure.

# BinarySearch.py # Alan Richmond, Python3.codes import random anum = 9 # number to search for size = 10 # size of random array array = random.sample(list(range(1, 20)), size) # get some random numbers array = sorted(array) # sorted() returns a new list #array.sort() # sort() sorts in-place print(anum, array) # show us what you've got # Search for number in array def binary_search(number, array, lo, hi): if hi < lo: return -1 # no more numbers mid = (lo + hi) // 2 # midpoint in array if number == array[mid]: return mid # number found here elif number < array[mid]: return binary_search(number, array, lo, mid - 1) # try left of here else: return binary_search(number, array, mid + 1, hi) # try above here def my_search(anum, array): # convenience interface to binary_search() return binary_search(anum, array, 0, len(array) - 1) pos = my_search(anum, array) if pos < 0: print("not found") else: print("found at position", pos)

- Popular Sorting Algorithms
- A Neural Network in Python, Part 1: sigmoid function, gradient descent & backpropagation
- Easy Graph Plotting with Pyplot
- A Quick Introduction to Python 3 Programming
- Spectral Harmonographs
- Editors & IDEs
- Eight Queens Puzzle - Six Lines
- Square Spiral
- Binary Search
- Fractal Tree

AI
assignment
bit operations
boolean
chr
color
colorsys
complex
conditionals
cos
data types
def
dict
eval
events
float
for
fractal
function
graphics
HSV
import
input
libraries
list
loop
math
matplotlib
modulo
not
numpy
pillow
print
pyaudio
pygame
random
range
recursion
RGB
search
simulation
sin
tuple
turtle
while

%d bloggers like this:

[…] useful in many applications, because sorted data can be searched or merged very quickly (e.g. by binary search). A sorted data set is one where every item is greater than its left neighbour (if any) and less […]

[…] are other implementations available that make use of different constructs including […]