How to implement binary search in python?

Binary Search

Intro

This document is aimed to show how to implement binary search algorithm in python programming language. It is assumed that the reader has knowledge of coding norms such as loops, functions. Also basic python experience is recommended.

1. Definition

Binary search is a searching algorithm that efficiently improves searching on sorted input datas.

2. Algorithm

(Assume data is sorted array.)
  1. get middle element of the data
  2. if middle(data) equals to search_key stop
  3. if search_key is lower than the middle than drop higher half of the data and turn step 1
  4. else if search key is higher than the middle than drop lower half of the data and turn step 1

3. Sample Working Illustration

3. Implementation on Python

To implement binary search in Python we can define binary search function like below

def binarySearch(data, target):
    min = 0
    max = len(data) - 1
    found = False
    while min <= max and not found:
        mid = (min + max) // 2 # floor
        if data[mid] == target:
            found = True
        else:
            if data[mid] > target:
            max = mid - 1
        elif data[mid] < target:
            min = mid + 1
   return found

4. Test

To test our function we can use following test function that generates sample sorted array and random index to test our function.

import random

def test():
    datasize = 10
    data = list(set([random.randrange(0,50,1)]) for x in range(datasize))
    key = data[random.randrange(0, len(data), 1)]

    found = binarySearch(data, key)

    print ("sample data")
    print ("size     : ", datasize)
    print ("data     : ", data)
    print ("searchkey: ", key)
    print ("found    : ", found)