Binary Search
Binary Search Overview
Count: 10
This section covers Binary Search, which is an efficient algorithm for searching a sorted array for a target value.
We'll focus on how to visualize the algorithm, and how visualization can help us when we are implementing the algorithm. We'll then look at some practice questions involving Binary Search.
The classic Binary Search algorithm is used to search for a target value in a sorted array.
DESCRIPTION
Given a sorted array of integers nums and a target value target, write a function to determine if target is in the array. If target is present in the array, return its index. Otherwise, return -1.
Example 1:
Input:
nums = [-1,0,3,5,9,12], target = 9Output: 4 (nums[4] = 9)
Example 2:
Input:
nums = [-1,0,3,5,9,12], target = 2Output: -1 (2 is not in the array, so we return -1.)
The appeal of Binary Search is readily apparent when we compare it to the brute-force approach.
The graphic below shows how the brute-force approach searches the sorted array for the target value 6. The elements considered during the search are highlighted in darker color.
Compare that to Binary Search, which locates 6 after only 3 "steps":
These two graphics show the efficiency of Binary Search, which performs the search in O(log n) time, compared to the much slower O(n) time of the Brute-Force Approach.
Intuition
Binary Search is efficient because it repeatedly cuts the portion of the array that needs to be searched in half.
Some of the visuals below are animated. Click on the to the left of each visual to start the animation.
Binary Search works because our array is sorted, and the middle element of a sorted array is a great starting point. All the elements to the left of the middle element are smaller than or equal to it, and all the elements to the right are larger than or equal to it.
Let's say our target is 6.
Since our target is greater than the middle element, we can safely ignore the left half of the array - we know the target is not there. We indicate this in the visual by turning those elements gray.
This leaves the right half of the array to search, and we've cut the search space in half for the first time.
How do we search the right half? With the same approach! We take the middle element of the right half (8), and compare it to the target.
Since our target is less than the middle element, we can now ignore the right half of the updated search space. We've just cut the search space in half again!
Now our search space has only two elements. By convention, we choose the first of these two elements as the "middle". Our target is equal to the middle element, meaning we've found it!
Key Takeaway
Binary Search works by repeatedly cutting the relevant search space of the array in half, until it either finds the target or the search space is empty, at which point it concludes that the target is not in the array. The halving is where the algorithm gets its O(log n) time complexity.
Implementation
Variables
Before diving into the code, let's first learn what each variable represents in the Binary Search algorithm, and visualize how they change during the search.
For these visualizations, target = 6 and nums = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10].
- Initialize two pointers, left and right, to the start and end of the array, respectively. These two pointers represent the search space of the array. Since the entire search space is valid, they are shown in green.
Next, we iteratively halve the search space until we've either found the target or the search space is empty (we will learn how to visualize this in the next section).
So while left <= right:
- Initialize a pointer mid = (left + right) // 2. mid represents the middle of the current search space, as well as the element that we compare to target.
- Compare the element at mid to the target. In this case, target > nums[mid], so we drop the left half of the search space by updating left = mid + 1. The elements that have been dropped are shown in gray.
-
At this point, left and right reflect the updated search space. So set mid = (left + right) // 2 again, and repeat the process until either nums[mid] == target or left > right.
target = 6
Code
Let's see the code!
Visualization
Python
Try these examples:
def binary_search(nums, target):left = 0right = len(nums) - 1while left <= right:mid = (left + right) // 2if nums[mid] == target:return midif nums[mid] < target:left = mid + 1else:right = mid - 1return -1
binary search for 6
0 / 7
Edge Cases
To deepen our understanding of Binary Search, let's consider some edge cases:
Empty Array
If the input array is empty, left starts at 0, right starts at -1, and the loop will not run, and we will return -1.
target = 2, nums = []
Visualization
Python
def binary_search(nums, target):left = 0right = len(nums) - 1while left <= right:mid = (left + right) // 2if nums[mid] == target:return midif nums[mid] < target:left = mid + 1else:right = mid - 1return -1
binary search for 2
0 / 2
Single Element Array
If the input array has only one element, left, mid, and right will all be the same, and the loop will run once. If the single element is the target, we return its index. Otherwise, left > right, so we exit the loop and return -1.
target = 2, nums = [1]
Visualization
Python
def binary_search(nums, target):left = 0right = len(nums) - 1while left <= right:mid = (left + right) // 2if nums[mid] == target:return midif nums[mid] < target:left = mid + 1else:right = mid - 1return -1
binary search for 2
0 / 4
Target Not in Array
If the target is not in the array, left will eventually be greater than right, and we will return -1.
target = 2, nums = [1, 3, 4, 8]
Visualization
Python
def binary_search(nums, target):left = 0right = len(nums) - 1while left <= right:mid = (left + right) // 2if nums[mid] == target:return midif nums[mid] < target:left = mid + 1else:right = mid - 1return -1
binary search for 2
0 / 6
This example helps us visualize the termination condition of Binary Search.
When left = right, as shown below, there is still one element in the search space, highlighted in green.
However, when left > right, as shown below, the search space is empty, and we know that the target is not in the array. We can visualize the binary search algorithm stopping when the left pointer "passes" the right pointer.
These visualizations should help you internalize why the condition left <= right is used in the Binary Search algorithm - once left overtakes right, the search space is empty and we know that the target is not in the array.
Test Your Knowledge
Login to take the complexity quiz and track your progress
Complexity Analysis
Time Complexity: O(log n) where n is the number of elements in the input array. We are halving the search space at each step.
Space Complexity: O(1) We are using a constant amount of space for the pointers, regardless of the size of the input array.
Summary
Binary Search is an effective algorithm because it allows us to repeatedly cut our search space in half until we find the target or conclude that it is not in the array. In other words, during each iteration of the algorithm, we are able to discard half of the search space.
Here are some problems that also use this concept of repeatedly discarding half of the search space:
Done | Question | Difficulty |
|---|---|---|
Medium | ||
Medium | ||
Hard | ||
Medium | ||
Hard |
Mark as read
Unlock Premium Coding Content
Reading Progress
On This Page
Your account is free and you can post anonymously if you choose.