GH avatar Bite 40. Write a binary search algorithm

There are many ways to search for an item in an ordered collection. One of the slowest methods is to check each single item from beginning to end. A more popular algorithm is binary search:

In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the middle element of the array; if they are unequal, the half in which the target cannot lie is eliminated and the search continues on the remaining half until it is successful. If the search ends with the remaining half being empty, the target is not in the array.

Your task today, should you decide to accept it, is to implement a binary search algorithm. Yes, Python has built in features that make this a no-brainer, but it’s also good to know how some things are done under the hood. It’ll make you a better programmer in the long run.

Special thanks to Martin Uribe for delivering this challenge.

33 out of 33 users completed this Bite.
Will you be Pythonista #34 to crack this Bite?
It takes an average of ~58 minutes to solve this Bite (submissions 5-240 min).
Pythonistas rate this Bite 7.0 on a 1-10 difficulty scale.
» Up for a challenge? 💪

Login and get coding
We use Python 3.7