Binary Search Algorithm
Tags: algorithms, tutorial, python
Published: 2020-09-29 14:52:14

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.

<br>
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.
<br>
 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

```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.