Day 16 of 30 days of Data Structures and Algorithms and System Design Simplified — Binary Search
Welcome back peeps. Hope all’s well. In this post we will cover Binary Search as follows —
What and Why Binary Search (in 2–3 sentences)?
How does Binary Search work?
Important Patterns and Techniques in Binary Search Questions
Most Important Questions with Solutions
Tips and Techniques to solve Binary Search Questions Fast.
Projects Videos —
All the projects, data structures, SQL, algorithms, system design, Data Science and ML , Data Analytics, Data Engineering, , Implemented Data Science and ML projects, Implemented Data Engineering Projects, Implemented Deep Learning Projects, Implemented Machine Learning Ops Projects, Implemented Time Series Analysis and Forecasting Projects, Implemented Applied Machine Learning Projects, Implemented Tensorflow and Keras Projects, Implemented PyTorch Projects, Implemented Scikit Learn Projects, Implemented Big Data Projects, Implemented Cloud Machine Learning Projects, Implemented Neural Networks Projects, Implemented OpenCV Projects,Complete ML Research Papers Summarized, Implemented Data Analytics projects, Implemented Data Visualization Projects, Implemented Data Mining Projects, Implemented Natural Leaning Processing Projects, MLOps and Deep Learning, Applied Machine Learning with Projects Series, PyTorch with Projects Series, Tensorflow and Keras with Projects Series, Scikit Learn Series with Projects, Time Series Analysis and Forecasting with Projects Series, ML System Design Case Studies Series videos will be published on our youtube channel ( just launched).
Subscribe today!
System Design Case Studies — In Depth
Design Instagram
Design Messenger App
Design Twitter
Design URL Shortener
Design Dropbox
Design Youtube
Design API Rate Limiter
Design Web Crawler
Design Facebook’s Newsfeed
Design Yelp
Design Uber
Design Tinder
Design Tiktok
Design Whatsapp
Most Popular System Design Questions
Mega Compilation : Solved System Design Case studies
Binary Search
Importance : Very High
Note : New Binary Search questions with solutions are added everyday. So keep checking this post daily.
Let’s dive in!
What is Binary Search?
Binary search is a very efficient search technique in which the searching follows divide and conquer strategy on the sorted arrays.
It reduces the search space by half with every iteration which makes it very efficient algorithm as compared to the linear search when it comes to searching in huge amount of data.
Examples of Binary Search problems —
Search element in a circular sorted array
Search a 2D Matrix
Search in rotated sorted array
Find Peak elemnt
Binary Search Tree traversals
Subarray Sum
Median of two sorted array etc
How does Binary Search work?
Binary search works on the principle of divide and conquer.
Binary Search is efficient as compared to linear search as it reduces the number of elements to be checked by half with each comparison.
Binary search works by repeatedly dividing the array in half, until the target element is found or it is determined that the element does not exist in the array. The algorithm starts by considering the middle element of the array and comparing it to the target element. If the middle element is equal to the target element, the algorithm returns the index of the middle element. If the middle element is less than the target element, the algorithm continues the search in the upper half of the array. If the middle element is greater than the target element, the algorithm continues the search in the lower half of the array. The search continues until the target element is found or the search interval is empty.
The given array is sorted and the two pointers left and right which are positioned at the beginning ( index 0 ) or end ( last index)of the array respectively.
Once positioned, calculate the mid = left + right/2
The mid will point to the mid element of the array. If the element at the mid is the target element then return the mid index
If the mid element is not the target element, then if the target element is smaller than mid element, shift the right pointer to the mid-1 index and again iterate from step 1. The remaining right array from the mid will be discarded.
If the mid element is not the target element, then if the target element is greater than mid element, shift the left pointer to the mid+1 index and again iterate from step 1. The remaining left array to the mid will be discarded.
Discarding the array based on the condition improves the time complexity.
There are two ways in which binary search algorithm can be implemented —
Iterative approach
Recursive Approach
Important Patterns and Techniques in Binary Search Questions
Some important patterns and techniques in binary search questions include:
- Divide and conquer: This technique is used to break down a problem into smaller subproblems, and is often used to search for a specific element or value in an array.
- Recursion: This technique is used to solve problems by breaking them down into smaller subproblems, and is often used to implement a binary search algorithm.
- Iteration: This technique is used to solve problems by repeatedly applying a specific operation, and is often used to implement a binary search algorithm.
- Lower and upper bound: This technique is used to find the first and last occurrence of a specific element in an array, and it can be used to solve many different types of problems.
- Time and space complexity: It’s important to understand the time and space complexity of a binary search algorithm and how it can be optimized for specific use cases.
Binary Tree questions have patterns such as —
- Array is sorted
- Tree is BST ( search in a BST)
- Min and Max array
- Intersection of two arrays
In the iterative Binary Search, the iterations for the binary search is done using loops
In recursive, the binary search function is called recursively.
Patterns → Questions like below belong to Binary Search( not limited to):
Intersection of two arrays
Split array Largest sum
Find Right Interval
Search element in a circular sorted array
Search a 2D Matrix
Search in rotated sorted array
Find Peak elemnt
Binary Search Tree traversals
Subarray Sum
Median of two sorted array etc
Most Important Questions with Solutions
Note : New Binary Search questions with solutions are added everyday. So keep checking this post daily.
Golden rule is — Learn by doing/implementing
In this we will see most important Binary Search questions.
Search a 2D Matrix
Question —
Write an efficient algorithm that searches for a value target in an m x n integer matrix matrix. This matrix has the following properties:
- Integers in each row are sorted from left to right.
- The first integer of each row is greater than the last integer of the previous row.
Example :
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: trueSolution :
Main Logic/Idea —
The main logic is to use binary search to identify which row and column to search in for the target element. Iterate through top and bottom and left and right to calculate mid and increment/decrement the pointers accordingly in order to efficiently implement the binary search on the 2D matrix.
Implementation —
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
row,col = len(matrix),len(matrix[0])
top,bottom =0,row-1
while top <= bottom:
row = (top + bottom)//2
if target > matrix[row][-1]:
top = row +1
elif target < matrix[row][0]:
bottom = row-1
else:
break
if not ( top <= bottom):
return False
row = (top+bottom)//2
left,right = 0,col-1
while left <= right:
mid = (left+right)//2
if target > matrix[row][mid]:
left = mid+1
elif target < matrix[row][mid]:
right = mid -1
else:
return True
return FalseQuestion Link
Similar Pattern —
Full Code Video Explanation ( In progress. Subscribe today for updates) :
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
Binary Search
Question —
Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.
You must write an algorithm with O(log n) runtime complexity.
Example 1:
Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4Solution :
Main Logic/Idea —
The given array is sorted and the two pointers left and right which are positioned at the beginning ( index 0 ) or end ( last index)of the array respectively. Once positioned, calculate the mid = left + right/2
The mid will point to the mid element of the array. If the element at the mid is the target element then return the mid index.
If the mid element is not the target element, then if the target element is smaller than mid element, shift the right pointer to the mid-1 index and again iterate from step 1. The remaining right array from the mid will be discarded.
If the mid element is not the target element, then if the target element is greater than mid element, shift the left pointer to the mid+1 index and again iterate from step 1. The remaining left array to the mid will be discarded.
Implementation —
def search(self, nums: List[int], target: int) -> int:
left, right =0,len(nums) -1
while left <= right:
m = (left+right)//2
if target < nums[m]:
right = m -1
elif target > nums[m]:
left = m +1
else:
return m
return -1Question Link
Similar Pattern —
Full Code Video Explanation ( In progress. Subscribe today for updates) :
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
Search Insert Position
Question —
Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You must write an algorithm with O(log n) runtime complexity.
Example :
Input: nums = [1,3,5,6], target = 5
Output: 2Solution :
Main Logic/Idea —
Use above logic ( as pervious question) to find the index to insert the target element can be inserted.
Implementation —
def searchInsert(self, nums: List[int], target: int) -> int:
left, right = 0, len(nums)-1
while left <= right:
mid = (left+right)//2
if target == nums[mid]:
return mid
elif target > nums[mid]:
left = mid+1
else:
right = mid -1
return leftQuestion Link
Similar Pattern —
Full Code Video Explanation ( In progress. Subscribe today for updates) :
Note : New Binary Search questions with solutions are added everyday. So keep checking this post daily.
Complexity Analysis
Read complexity analysis post before calculating binary search complexity.
Since the search space is divided by 2 in every iteration of the array :
Best Case time complexity : O(1)
Average Case time complexity : O(logn)
Worst Case time complexity : O(logn)
Tips and Techniques to solve Binary Search Questions Fast.
Binary search is used where every its given —
Find the solution in log n time
Array is sorted
Questions that asks for average time
Binary Search Tree traversals and search for node in BST
Min and Max Array
Sorted Sub array sum.
That’s it for now. Day 17 : Hashing coming soon !
Let me know if you have questions in the comment section below. Subscribe/ Follow, Like/Clap as it will encourage me to write more in my free time and Stay Tuned!!
Read More —
11 most important System Design Base Concepts
6. Networking, How Browsers work, Content Network Delivery ( CDN)
13. System Design Template — How to solve any System Design Question
Some of the other best Series —
30 days of Data Structures and Algorithms and System Design Simplified
Data Science and Machine Learning Research ( papers) Simplified **
100 days : Your Data Science and Machine Learning Degree Series with projects
Complete Data Visualization and Pre-processing Series with projects
Exceptional Github Repos — Part 1
Exceptional Github Repos — Part 2
Tech Newsletter —
If you are interested, you can join my newsletter through which I send tech interview tips, techniques, patterns, hacks — Software Development, ML, Data Science, Startups and Technology projects to more than 30K readers. You can subscribe to Tech Brew :
For Python Projects —
For complete 60 days of Data Science and ML : Day 1 — Day 60 : Quick Recap of 60 days of Data Science and ML
Follow for more updates. Stay tuned and keep coding!
For other projects, tune to —
Build Machine Learning Pipelines( With Code)
Recurrent Neural Network with Keras
Clustering Geolocation Data in Python using DBSCAN and K-Means
Facial Expression Recognition using Keras
Hyperparameter Tuning with Keras Tuner
Custom Layers in Keras
