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:

1. Start with a sorted array and the target element you want to find.
2. Compare the target element with the middle element of the array.
3. If the target element matches the middle element, the search is successful, and the algorithm returns the index of the middle element.
4. If the target element is less than the middle element, the search continues in the left half of the array.
5. If the target element is greater than the middle element, the search continues in the right half of the array.
6. 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:

1. Initialize two pointers, left and right, pointing to the start and end of the search space, respectively.
2. 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.
3. 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:

• Leetcode - Binary Search