Binary search is a powerful and efficient algorithm used to search for a specific element in a sorted array. It follows a divide-and-conquer approach, repeatedly dividing the search interval in half until the target element is found or the interval is empty. In this blog post, we’ll explore the concept of binary search and implement it using Swift.
How Binary Search Works
The binary search algorithm works on the principle of reducing the search space by half at each iteration. Here’s how it works:
- Start with a sorted array and the target element you want to find.
- Compare the target element with the middle element of the array.
- If the target element matches the middle element, the search is successful, and the algorithm returns the index of the middle element.
- If the target element is less than the middle element, the search continues in the left half of the array.
- If the target element is greater than the middle element, the search continues in the right half of the array.
- Repeat steps 2-5 until the target element is found or the search space is exhausted.
The binary search algorithm has a time complexity of O(log n), making it highly efficient for large datasets.
Binary Search in Swift
Implementing
Let’s implement the binary search algorithm in Swift:
func binarySearch<T: Comparable>(_ array: [T], target: T) -> Int? {
var low = 0
var high = array.count - 1
while low <= high {
let mid = (low + high) / 2
let midElement = array[mid]
if midElement == target {
return mid
} else if midElement < target {
low = mid + 1
} else {
high = mid - 1
}
}
return nil
}
In this implementation:
- The
binarySearch
function takes a sorted array of comparable elements and the target element to search for. - We initialize two pointers,
low
andhigh
, representing the start and end indices of the search space. - We enter a loop that continues as long as
low
is less than or equal tohigh
. - Inside the loop, we calculate the middle index
mid
and retrieve the middle elementmidElement
. - We compare
midElement
with the target element:- If they are equal, we have found the target and return its index.
- If
midElement
is less than the target, we updatelow
tomid + 1
to search in the right half. - If
midElement
is greater than the target, we updatehigh
tomid - 1
to search in the left half.
- If the loop exits without finding the target element, we return
nil
to indicate that the element was not found.
Example Usage
Here’s an example of how to use the binarySearch
function:
let numbers = [1, 3, 5, 7, 9, 11, 13, 15]
let target = 7
if let index = binarySearch(numbers, target: target) {
print("Element \(target) found at index \(index)")
} else {
print("Element \(target) not found")
}
Output:
Element 7 found at index 3
In this example, we have a sorted array of numbers and a target element of 7. We call the binarySearch
function with the array and target, and it returns the index of the target element if found, or nil
otherwise.
Problems
Problem: 287. Find the Duplicate Number
Leetcode: 287. Find the Duplicate Number
To solve this problem using binary search, we can leverage the fact that the numbers in the array are in the range [1, n]
. We can treat the range as a search space and perform binary search on it.
Here’s the step-by-step approach:
- Initialize two pointers,
left
andright
, pointing to the start and end of the search space, respectively. - While
left
is less than or equal toright
:- Calculate the midpoint
mid
as(left + right) / 2
. - Count the number of elements in the array that are less than or equal to
mid
. - If the count is greater than
mid
, it means the duplicate number is in the range[left, mid]
. Updateright
tomid - 1
. - Otherwise, the duplicate number is in the range
[mid + 1, right]
. Updateleft
tomid + 1
.
- Calculate the midpoint
- Return
left
as the duplicate number.
Here’s the Swift code implementation:
func findDuplicate(_ nums: [Int]) -> Int {
var left = 1
var right = nums.count - 1
while left < right {
let mid = left + (right - left) / 2
var count = 0
for num in nums {
if num <= mid {
count += 1
}
}
if count > mid {
right = mid
} else {
left = mid + 1
}
}
return left
}
print(findDuplicate([1,3,4,2,2])) // 2
print(findDuplicate([3,1,3,4,2])) // 3
print(findDuplicate([3,3,3,3,3])) // 3
In this code, we initialize left
and right
pointers to the start and end of the search space. We then perform binary search by calculating the midpoint mid
and counting the number of elements in the array that are less than or equal to mid
.
If the count is greater than mid
, it means the duplicate number is in the range [left, mid]
, so we update right
to mid
. Otherwise, the duplicate number is in the range [mid + 1, right]
, and we update left
to mid + 1
.
We continue the binary search until left
and right
pointers meet, at which point left
will be pointing to the duplicate number.
The time complexity of this solution is O(n log n)
since we perform binary search on the range [1, n]
and count the elements in the array for each iteration. The space complexity is O(1)
as we only use constant extra space.
Problem: 268. Missing Number
Leetcode: 268. Missing Number
Here’s the step-by-step approach:
- Sort the input array.
- Use binary search to find the first index i where nums[i] != i. This index represents the missing number.
- If no such index is found, it means the missing number is n.
func missingNumber(_ nums: [Int]) -> Int {
let sortedNums = nums.sorted()
let n = nums.count
var left = 0
var right = n
while left < right {
let mid = left + (right - left) / 2
if sortedNums[mid] > mid {
right = mid
} else {
left = mid + 1
}
}
return left == n ? n : left
}
print(missingNumber([3,0,1])) // 2
print(missingNumber([0,1])) // 2
print(missingNumber([9,6,4,2,3,5,7,0,1])) // 8
- We start by sorting the input array nums using sortedNums = nums.sorted().
- We initialize left to 0 and right to n (the length of the array).
- We perform binary search in the while loop:
- Calculate the middle index mid.
- If
sortedNums[mid]
is greater thanmid
, it means the missing number is on the left side ofmid
. So, we updateright
tomid
. - Otherwise, the missing number is on the right side of
mid
, so we updateleft
tomid + 1
.
- After the loop terminates,
left
will be equal to the missing number if it’s less thann
. Ifleft
is equal ton
, it means the missing number isn
.
The time complexity of this solution is O(n log n)
due to the sorting step and the binary search. The space complexity is O(1)
since we’re not using any additional data structures that grow with the input size.
Problem: 4. Median of Two Sorted Arrays
Leetcode: 4. Median of Two Sorted Arrays
func findMedianSortedArrays(_ nums1: [Int], _ nums2: [Int]) -> Double {
// We first ensure that nums1 is the smaller array by swapping them if necessary. This simplifies the binary search logic.
if nums1.count > nums2.count {
return findMedianSortedArrays(nums2, nums1)
}
let m = nums1.count
let n = nums2.count
// We initialize iMin and iMax to represent the range of indices in nums1 where we will perform the binary search.
var iMin = 0, iMax = m
let halfLen = (m + n + 1) / 2
// We start a binary search loop that continues as long as iMin is less than or equal to iMax.
while iMin <= iMax {
// We calculate the middle index i of nums1 and the corresponding index j in nums2 using halfLen.
let i = (iMin + iMax) / 2
let j = halfLen - i
// We compare the elements at indices i-1 in nums1 and j-1 in nums2 to determine which half of the arrays to search next.
if i < m && nums2[j-1] > nums1[i] {
// If the element at j-1 in nums2 is greater than the element at i in nums1, we update iMin to i+1 to search the right half of nums1.
iMin = i + 1
} else if i > 0 && nums1[i-1] > nums2[j] {
// If the element at i-1 in nums1 is greater than the element at j in nums2, we update iMax to i-1 to search the left half of nums1.
iMax = i - 1
} else {
// If neither of the above conditions is true, we have found the correct partition.
// We calculate maxLeft as the maximum element between nums1[i-1] and nums2[j-1].
var maxLeft = 0
if i == 0 {
maxLeft = nums2[j-1]
} else if j == 0 {
maxLeft = nums1[i-1]
} else {
maxLeft = max(nums1[i-1], nums2[j-1])
}
// if the total length of both arrays is odd, we return maxLeft as the median.
if (m + n) % 2 == 1 {
return Double(maxLeft)
}
// If the total length is even, we calculate minRight as the minimum element between nums1[i] and nums2[j].
var minRight = 0
if i == m {
minRight = nums2[j]
} else if j == n {
minRight = nums1[i]
} else {
minRight = min(nums1[i], nums2[j])
}
// We return the average of maxLeft and minRight as the median.
return Double(maxLeft + minRight) / 2.0
}
}
return 0.0
}
print(findMedianSortedArrays([1, 3, 7, 8], [4, 6])) // 5
print(findMedianSortedArrays([1, 3, 7, 8, 9], [4, 6])) // 6
print(findMedianSortedArrays([ -5, 3, 6, 12, 15], [-12, -10, -6, -3, 4, 10])) // 3
Conclusion
Binary search is a powerful algorithm for efficiently searching sorted arrays. By repeatedly dividing the search space in half, it achieves a logarithmic time complexity, making it suitable for large datasets. With the Swift implementation provided in this blog post, you can easily incorporate binary search into your own projects and solve various data structure and algorithm problems efficiently.
Further Readings: