Binary Search
So you have mastered the basic string and array problems. Awesome. Now we will be moving on to Binary Search. Binary Search is the most common searching mechanism, and really the only one seen in Leetcode problems. Let's give an overview of how Binary Search works, and why it is better than a common linear search.
So Swift has a built in method of searching for an element in an array, we could simply do:
let array = [1, 2, 3, 4, 5, 6, 7]
if let indexOfElement = array.firstIndex(of: 3) {
print(indexOfElement)
}
// 2
Using the built-in Swift search, we can search our entire array to find the index of the element we are searching for. This is great if our element is in the beginning of the array, but if our element is at the very end of the array it becomes very time consuming. The built in Swift search, is a linear search, which gives us on average O(n) time. If our array has 1 million elements, it will on average take us 1 million steps to find the element. Ouch.
This is where Binary Search comes in. Binary Search takes O(Log(n)) time on average. So our 1 million element array, will only take us about 20 steps on average to find the element. Awesome. BUT, there is a downside to the Binary Search, and that is the array must be sorted in order. We will see why that is the case.
The way Binary Search works is:
- Find which half of the array our element is in (Left half vs Right half)
- If the element is in the right half, we repeat this process with the right half of the array (and vice-versa for left half)
- Repeat until the element is found
- If we cannot split the array anymore, our element doesn't exist in our array
As you can now see, we must have a sorted array when doing Binary Search. We can easily find which half of the array our element resides in, with a simple comparison operator like < or >. You will often hear Binary Search referred to as "Divide and Conquer" for this reason.
Implementation
Binary Search can be implemented both recursively and iteratively.
Recursive
The recursive implementation is very straight forward.
func binarySearch(_ array: [Int], key: Int, range: Range<Int>) -> Int? {
if range.lowerBound >= range.upperBound {
// If we get here, then the search key is not present in the array.
return nil
} else {
// Calculate where to split the array.
let midIndex = range.lowerBound + (range.upperBound - range.lowerBound) / 2
// Is the search key in the left half?
if array[midIndex] > key {
return binarySearch(array, key: key, range: range.lowerBound ..< midIndex)
// Is the search key in the right half?
} else if array[midIndex] < key {
return binarySearch(array, key: key, range: midIndex + 1 ..< range.upperBound)
// If we get here, then we've found the search key!
} else {
return midIndex
}
}
}
let numbers = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67]
if let result = binarySearch(numbers, key: 43, range: 0 ..< numbers.count) {
print(result) // gives 13
}
Pay a close bit of attention on how we anchor our left vs right halves of our array. The equation range.lowerBound + (range.upperBound - range.lowerBound) / 2 is something you should remember as we can split both even and odd numbered arrays with this equation. Every time we find our element is in the left or right half of the array, we recursively pass the range of the new array back into our function. This saves us space by not having to keep variables for the left and right halves of the array.
It is also worth noting, that recursive implementations inherently come with O(n) space, due to our machine holding the function call stack in memory. Because of this, the iterative approach is favored here, for efficiency sake.
Iterative
The following is the iterative approach to the Binary Search:
func binarySearch(_ array: [Int], key: Int) -> Int? {
var lowerBound = 0
var upperBound = array.count
while lowerBound < upperBound {
let midIndex = lowerBound + (upperBound - lowerBound) / 2
if array[midIndex] == key {
return midIndex
} else if array[midIndex] < key {
lowerBound = midIndex + 1
} else {
upperBound = midIndex
}
}
return nil
}
let numbers = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67]
if let result = binarySearch(numbers, key: 43) {
print(result) // gives 13
}
Many recursive functions can be converted to iterative functions by using loops. Note the while loop here.
So that is Binary Search and how it works under the hood. Let's apply this to some Leetcode problems!
Search in Rotated Sorted Array
Time to apply that Binary Search knowledge!
This one can be a little tricky. We know from the intro in this article, that Binary Search takes a sorted array. But the input array in this problem is sorted around a pivot. So we cannot use Binary Search out of the box, we need to alter it a little. Considering the problem statement says our solution must be in O(logN) time, there really is no point figuring out a brute force, O(n) solution. Let's get into the Binary Search solution.
[ Altered Binary Search ]
[ O(logN) time + O(1) space ]
We need to think about how our input array is structured. We can still use Binary search in a way but we must be methodical. We know we will have a left pointer, right pointer & middle pointer of our array. The question is though, is our middle element, in the left sorted half, or right sorted half? If our input array is [4, 5, 6, 7, 0, 1, 2] our midpoint will be 7. We know that 7 (our midpoint) is in the left sorted half of the array. How do we know this?
Well we can compare our midpoint to our leftPointer. If our midpoint is greater than or equal to our left pointer, our midpoint belongs in the left half of the array. Let's see another example. Say our input array is [7, 0, 1, 2, 3]. In this case our midpoint is not greater than or equal to our left pointer, thus our midpoint belongs to the right half of our array. Ok cool. Now what do we do when we figure out what side our midpoint belongs to?
Once we figure out which side of the array our midpoint belongs to, we can see if our target falls within the range of that side of the array. For example, say our input array is [4, 5, 6, 7, 0, 1, 2], we know the midpoint belongs to the left side of the array. So within the left side of the array, we need to check if our target falls in that range. If it does we need to search that half, if it doesn't we need to search the other side of the array. Our target in the example problem is 0. Considering we know the midpoint belongs to the left side of the array, we should compare our target to the array [4, 5, 6, 7]. Does our target fall within that range? No it doesn't, so we should check the other half of the array [0, 1, 2]. Then we repeat this process continuously until we find our element.
In pseudocode:
while leftPointer less than or equal to rightPointer
if our midpoint is greater than or equal to our left pointer, midpoint is in the left half of the array
if our target is in range of the left side of the array
repeat search on the left side of the array
else our target is out of range of the left side of the array
repeat search on the right side of the array
else our midpoint is in the right side of the array
if our target is in range of the right side of the array
repeat search on the right half of array
else our target is out of range of the right side of the array
repeat search on the left half of the array
That gets a little wordy! But it outlines our intent very well. As discussed here earlier, the time complexity is O(logN) due to Binary Search, and O(1) space because we are not storing anything here. The real implementation is as follows:
var leftPointer = 0
var rightPointer = nums.count - 1
while leftPointer <= rightPointer { // While our pointers are still valid
let mid = leftPointer + (rightPointer - leftPointer) / 2 // Find the midpoint of our array
if nums[mid] == target { return mid } // We have found our element!
if nums[leftPointer] <= nums[mid] { // Our midpoint is in the left half of the array
if target > nums[mid] || target < nums[leftPointer] { // Target is not in range of the left half
leftPointer = mid + 1 // Move left pointer
} else { // Target is in range of the left half
rightPointer = mid - 1 // Move right pointer
}
} else { // Our midpoint is in the right half of the array
if target < nums[mid] || target > nums[rightPointer] { // Target is not in range of the right half
rightPointer = mid - 1 // Move right pointer
} else {
leftPointer = mid + 1 // Move left pointer
}
}
}
return -1
Well Done!
---
Find Minimum in Rotated Sorted Array
This problem is actually more straight forward than our last one.
There should be a couple flags here that let us know this is a Binary Search array type problem. First, the problem states the input array is in sorted (but rotated) order, and second, we need an O(LogN) time solution. When we see a combination of these two things, we know it is most likely a Binary Search problem.
[ Altered Binary Search ]
[ O(logN) time + O(1) space ]
This approach is like a slightly altered version of Binary Search. Since our input array is sorted but rotated an unknown amount of times, we don't exactly know where our pivot point is. If we take a look at the previous problem, we can check the midpoint and compare it to the rightmost array element to see if our midpoint belongs to the left or right side of the array. Using that information we can search the right and left arrays continuously until we run out of elements to search.
We will also want to keep a variable for the minimum element in the array. We can use our midpoint anchor to track which element is our smallest.
BUT, there is one situation we should also be aware of. If our array is sorted, based on our left and right pointers, we can break out of our loop, because we know the smallest element will be the leftmost element. Here is the pseudocode:
while leftPointer less than or equal to rightPointer
if our array is sorted
min is leftmost element
break from loop
update minimum element with midPointer as needed
if midPointer > rightPointer
search right half of the array
else search left half of array
As discussed here earlier, the time complexity is O(logN) due to Binary Search, and O(1) space because we are not storing anything here, aside from a minimum element variable. The real implementation is below:
var mini = Int.max // Some default value
var leftPointer = 0
var rightPointer = nums.count - 1
while leftPointer <= rightPointer { // While our pointers are still valid
guard nums[leftPointer] > nums[rightPointer] else { // If our array is sorted
mini = min(mini, nums[leftPointer]) // Update global minimum
break // Break from loop
}
let mid = leftPointer + (rightPointer - leftPointer) / 2
mini = min(mini, nums[mid]) // Update global minimum
if nums[mid] > nums[rightPointer] { // Midpoint belongs to the right half of the array
leftPointer = mid + 1
} else { // Midpoint belongs to the left half of the array
rightPointer = mid - 1
}
}
return mini
Conclusion
Keep an eye out when you see sorted input arrays, and problems that require O(logN) time complexity, this usually points to a classic Binary Search problem!
