Binary Search
How to efficiently determine if an element appears in an array
To get started in data structures and algorithms, it’s good to know the basic searching and sorting methods.
Here we will discuss the search algorithm known as binary search, how it works, and finally how to code it. Let’s begin!
We will assume that the input array is sorted. This will enable us to check for the presence of the desired element rapidly, without necessarily having to visit every number in the list.
We will start by checking in the middle. If don’t find it there, we will move left or right, depending on whether our desired number is higher or lower than the number at this position.
If, for example, the number we’re seeking is lower than this “candidate” number in the middle, then we should shift our window to the subset of numbers on the left hand side. We do this by resetting our right-hand pointer to the position left of the middle candidate we just checked.
Conversely, if the desired number is higher than the candidate, then we will look to the right by modifying our left-hand pointer.
This process continues until we have exhausted all the numbers in the relevant sub-portion of the array. We will know that this has occurred once the left and right pointers “cross” each other.
Here is one way to implement this algorithm in Python:
def binary_search(num,arr):
left = 0
right = len(arr) - 1
while left <= right: # stop searching when pointers cross
middle = (left + right)//2
if num == arr[middle]:
return middle
if num > arr[middle]:
left = middle + 1
if num < arr[middle]:
right = middle - 1
return -1Check this on an example to make sure that it returns the expected results.
arr = [1,4,8,12,12,16,21,34,54,56,65,67,78,89,123]
test_nums = [78,3]
for num in test_nums:
print(binary_search(num,arr))>>> 12
>>> -1
As we hoped, the number 78 is found in position 12 (zero-based) and the number 3 returns -1 because it is not found in the array.
I hope this helps you in your path to understand and implement data structures and algorithms.
