Binary Search Algorithm

Binary search algorithm is an efficient algorithm that searches a sorted list for a desired or target element.

Binary search works by comparing the target value to the middle element of the list.
If the target value is greater than the middle element, the left half of the list is eliminated from the search space, and the search continues in the right half.

If the target value is less than the middle value, the right half is eliminated from the search space, and the search continues in the left half.

This process is repeated until the middle element is equal to the target value, or if the algorithm returns that the element is not in the list at all.

The Worst Case Time Complexity is O(log n)

Algorithm:

• The variable start is set to 0 and end is set to the length of the list.
• The variable start keeps track of the first element in the part of the list being searched while end keeps track of the element one after the end of the part being searched.
• A while loop is created that iterates as long as start is less than end.
• mid is calculated as the floor of the average of start and end.
• If the element at index mid is less than key (i.e. desired element) then start is set to mid + 1.
• If it is larger than key then end is set to mid.
• Otherwise, the element at mid index will be equal to key which is returned as the index of the found element.
• If no such item is found, -1 is returned.

Let's take an example, suppose we have following list:

List_Item	21	23	24	35	45	48	56	77	89
Index	0	1	2	3	4	5	6	7	8

And we want search if 24 is present in the list or not.

According to the algorithm we need to set some variables
start = 0 (index of first element)
end = 8 (index of last element)
mid = 4 = (0+8)/2 (index of middle element)

List_Item	21	23	24	35	45	48	56	77	89
Index	0	1	2	3	4	5	6	7	8
Positions	start				mid				end

Now we will arrange the variables according to current value of mid index i.e 48
If the element at index mid (i.e. 48 ) is less than 24 then start is set to mid + 1
And if the element at index mid (i.e.48) is larger than 24 then end is set to mid
Otherwise, the element at mid index will be equal to 24 which is returned as the index of the found element.


We can clearly see that 24 < list[mid], so we will make following changes.
start = 0 no changes
end = 4 current mid
mid = 2 = (0+4) / 2

List_Item	21	23	24	35	45	48	56	77	89
Index	0	1	2	3	4	5	6	7	8
Positions	start		mid		end

We will repeat this process until start < end. If start goes to less than end that mean element is not present in the list.

Now if we analyze the current positions of variable, we can clearly that 24 is equal to value of mid index. We will return this index.

Following is the implementaion of binary search algorithm in Python

def binary_search(mylist, key):
    """Search key in mylist [start... end - 1]."""
    start = 0
    end = len(mylist)
    while start < end:
        mid = (start + end)//2
        if mylist [mid] > key:
            end = mid
        elif mylist [mid] < key:
            start = mid + 1
        else:
            return mid
    return -1


mylist = input[21, 23, 24, 35, 45, 48, 56, 77, 89]
key = 24

index = binary_search(mylist, key)
if index < 0:
    print(key ,' was not found.’)
else:
    print(key , 'was found at index', index)

OUTPUT:

24 was found at index 2.

Comments

[Adish Jain]

Hey Atebar! Awesome post. I couldn't find how to contact you, but I wanted to share this interactive tutorial I wrote on Binary Search: getleaf.app/dsps301/binarysearch-k.... Would love to hear your thoughts & get your feedback.