Binary Search: Consider an example where you are given a phone book to find a name and are asked to find Taylor. As you know, the phone book is already sorted from A to Z.
Like most people you will not start looking from the first page. Instead, you will probably go to the middle section of the book and compare the section name with the initial of the name you are looking for. Taylor won’t be in the middle section of the book after your first iteration.
You can now be sure that it won’t be in the first half of the book. So, you can ignore the first half of the phone book, and you can repeat the above process again by going again to the middle from say, L to Z, till you find Taylor in section T.
This approach is an example of Divide and Conquer strategy, which divides the larger problem into smaller problems and solving those.
Steps of Binary Search Algorithm
The Binary search works in a similar fashion as the process described above, and can only be applied to sorted sequence. The algorithm starts by looking at the middle element, resulting in one of three possibilities:
- The middle item is the target value
- Target value is less than the middle item
- Target value is greater than the middle item
Since we are using sorted sequence in a binary search, we can ignore half the values in the list when the target is not found at the middle position.
The middle item is the target value:
Item at the middle is same as the target value, the algorithm returns True.
If the target value is smaller than the middle element:
Since the target value is smaller than the middle element, we will ignore / eliminate half the list from middle to the end of the list. Because, since the list is sorted, we can be sure that the target value can never be in the list after the middle element.
We can repeat the algorithm to include values from start till the middle of the list. And we can repeat the same process until target value is Found or Not Found.
If the target value is bigger than the middle element:
Likewise, if the target value is bigger than the middle element, we can ignore the first half of the list, and repeat the process for the remaining upper half of the list.
Binary search code in python
Iterative approach:
def BinarySearch(lst, target):
low = 0
high = len(lst)-1
while low<=high:
mid = (high+low)//2
if lst[mid] == target:
return True
elif target < lst[mid]:
high = mid - 1
else:
low = mid + 1
return FalseRecursive approach:
def binarySearch(lst,low, high, target):
if high >= low:
mid = (high + low) // 2
if lst[mid] == target:
return True
elif lst[mid] > target:
return binarySearch(lst, low, mid - 1, target)
else:
return binarySearch(lst, mid + 1, high, target)
else:
return FalseTime and Space Complexities
Time Complexities
- Best case complexity:
O(1) - Average case complexity:
O(log n) - Worst case complexity:
O(log n)
Space Complexity
The space complexity of the binary search is O(1).
Frequently Asked Questions:
How binary search works?
It starts by looking at the middle element, and three things can happen:
- The middle element is the target value
- The target value is less than the middle
- The target value is greater than the middle
The middle element is the target value, it returns True.
The target value is less than the middle, the upper half of the list is ignored, and algorithm only repeats from Low, i.e., 0 till the middle of the list and repeat till the target value is found or not found.
Target value is greater than the middle, the lower half of the list is ignored, and algorithm only repeats from middle till the end of the list and repeat till the target value is found or not found.
when to use binary search?
You should only use it when the list is sorted.
Does a list have to be in order for Binary Search?
Yes. The list should be in order for it to work.
What are the two types of binary search?
There are two types of binary search algorithms:
What is the real-life example of binary search?
You like to do daily journaling, and you have spent your last year doing daily journaling. Now you want you look at the journals from say, March 2022. You don’t start looking from the first page, turning the pages, till you react March. You start by looking at the middle page. It definitely isn’t March, so you ignore the upper half of the diary, because March can never be in that half.
So, you repeat the process to find the middle from Jan-July. You again look at the middle and it’s May. So again, you ignore the upper half and repeat the process until you are at March and now you can look at your journals from March.
What is the logic for binary search?
It is a searching algorithm which works by repeatedly dividing the list in half and checking the middle element.
Why is it called binary search?
It is based on ‘divide and conquer’ approach which requires the initial list to be sorted before searching. It is called binary because it splits the list into two halves.
Why is it faster than linear search algorithm?
Binary search is faster than linear because unlike linear search it doesn’t look at every element. For every iteration, the algorithm divides the list into two halves and checks the middle element and perform comparison to ignore the list, where the target value cannot possibly exist.
That is why, binary search offers an average time complexity O(log n) meanwhile linear offers O(n).
Advantages and Disadvantages:
Advantages
- It is better than the linear search before the average runtime complexity is O(log n) while Linear search is O(n).
- Binary search doesn’t look at every element in the list. Instead it divides the list into two halves and perform its operations.
Disadvantages
- It can only be used when the list is sorted.
- The process of sorting and searching in an unsorted array will take time. Thus, binary search is not a good option in such cases.
Conclusion
I am sure you now have solid understanding of what is Binary search and how it works.
We have covered everything from logic to the implementation and complexity of the algorithm.
Python code is also provided, using both Iterative and Recursive approaches.