Imagine that in a certain, problem you have to look for an integer in a list of numbers, using python you may have some ideas, let's try one of them : 

  • let's keep it simple and use a for loop  :
let's take a sorted array containing numbers from 0 to 100 , and search whether the value 49 
exist or no : 
l = [i for i in range(0,101)]
y = False
v = 49
for i in l :
    if i == v : y = True
if y == True : print(f'{v} in in the list')
else: print(f'{v} is not in the list')
well this solution is perfect for small integers like our example, but when the input get large this algorithm takes too much time to execute, because we are comparing every element of the list with the wanted element so time complexity is linear O(n) ==> when input get larger, the needed time increases.

and to overcome this issue, we use binary search in it's simplest form. The idea is about having a sorted list of integers ( there are many sorting method, you can see this article to learn more about them : Sorting algorithms ), and then we divide the list into two equal lists and see whether the wanted element is on the left of the middle element or on the right of this element, if it is on the right then probably the element exist in the right list, and vice versa. We keep doing this for the left or right list until having a list of one element, which is the wanted element, or having a list with no element, which means that this element is not in the list, this is a simple python code for binary search : 


def binary_search(l,v) :
    for i in range(len(l)):
        r = n - 1
        l1 = 0
        ok = False
        while r >= l1 :
            m = (r + l1) // 2 # the middle element
            if l[m] == v      # check whether the middle element equals the wanted element. 
                ok = True
                break
            elif l[m] < v :   # check whether the wanted element is on the right of m.      
                l1 = m + 1
            elif l[m] > v :   # check whether the wanted element is on the left of m.
                r = m - 1
        return ok










Buy Website Traffic