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