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`

and`high`

, 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 to`high`

. - Inside the loop, we calculate the middle index
`mid`

and retrieve the middle element`midElement`

. - 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 update`low`

to`mid + 1`

to search in the right half. - If
`midElement`

is greater than the target, we update`high`

to`mid - 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`

and`right`

, pointing to the start and end of the search space, respectively. - While
`left`

is less than or equal to`right`

:- 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]`

. Update`right`

to`mid - 1`

. - Otherwise, the duplicate number is in the range
`[mid + 1, right]`

. Update`left`

to`mid + 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 than`mid`

, it means the missing number is on the left side of`mid`

. So, we update`right`

to`mid`

. - Otherwise, the missing number is on the right side of
`mid`

, so we update`left`

to`mid + 1`

.

- After the loop terminates,
`left`

will be equal to the missing number if it’s less than`n`

. If`left`

is equal to`n`

, it means the missing number is`n`

.

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: