What is binary search?

  • Binary search is an advanced searching algorithm which is used to find an element in an array or list without searching the entire items.

How does binary search works?

  • Binary search will sort an array or list in ascending order first.
  • Binary search will compare the middle item with the item to be found. If they are equal then the search is completed.
  • If the item is not found then an array or list is divided into two parts with the help of index of middle item.
  • If the item is less than the middle item then left side half is considered else right side half is considered.
  • The search will continue until the item is found or last item is reached.

Example:

  • Consider yourself searching for a card in a deck of sorted cards.
  • Pick a card from the middle of the deck and compare it with your card if same then you found your card.
  • If the card is not found discard half of the deck where your card availability is not possible.
  • Repeat the above process until you find your card or reach the end of deck.
def binary_search(item,lst):
    lst.sort()
    first = 0
    last = len(lst) - 1
    item_found = False

    while first <= last:
        midpoint = (first+last)//2
        
        if item == lst[midpoint]:
            item_found = True
            break
        else:
            if item > lst[midpoint]:
                first = midpoint + 1
            else:
                last = midpoint - 1
    return item_found

Check the below link for source code:

https://github.com/NightFury5535/Python/blob/master/binary_search.ipynb