Data Structure: Binary Search with python

So let's say you want to find the number in a sorted list with a quick and easy.

There are two ways that you can do.

1. you can go one by one and check if the current element is the target element. suppose if we have 1000000 elements you will do it million times.

2. Using binary search

with binary search you can find your target element in log2 of N time. Suppose if we have 1000000 elements you will search only 20 times.

So how ?

binary Search

is a logarithmic search.

Time complexity (worse-case)

O(log N)

Noted

Binary search is only work with sorted list.

Code:

arr = [1,2,3,4,5,6,7]
target = 4

def binary_search(arr,target):
    low = 0
    high = len(arr) -1
    while low <= high:
        mid = (high + low) // 2
        guess = arr[mid]
        if target == guess:
           return mid

        if guess > target:
           high = mid
        else:
           low = mid
    return None