Binary Search Algorithms in Swift

1. Introduction

Binary Search is a search algorithm that finds the position of a target value within a sorted array or list. It significantly improves linear search by reducing the number of comparisons needed, hence increasing the speed of the search.

2. Implementation Steps

1. Start with the entire list and determine the middle element.

2. If the middle element equals the target value, return its index.

3. If the target value is less than the middle element, repeat the search with the left half of the list.

4. If the target value is greater than the middle element, repeat the search with the right half of the list.

5. Repeat steps 1-4 until the target value is found or the list is exhausted.

3. Implementation in Swift

func binarySearch<T: Comparable>(_ array: [T], _ target: T) -> Int? {
    var low = 0                                   // 1. Initialize the lower boundary.
    var high = array.count - 1                    // 2. Initialize the upper boundary.
    while low <= high {                           // 3. Continue while there's a segment to search.
        let mid = (low + high) / 2                // 4. Calculate the middle index.
        if array[mid] == target {                 // 5. Check if the middle element matches the target.
            return mid
        } else if array[mid] < target {           // 6. Adjust boundaries for the right half.
            low = mid + 1
        } else {                                  // 7. Adjust boundaries for the left half.
            high = mid - 1
        }
    }
    return nil                                    // 8. If the target value is not found, return nil.
}
// Example Usage
let sortedNumbers = [12, 29, 37, 40, 57, 68, 72, 93]
if let index = binarySearch(sortedNumbers, 57) {
    print("Found at index:", index)
} else {
    print("Not found.")
}

Output:

Found at index: 4

Explanation:

1. Binary Search requires the input array to be sorted. It then starts by defining the lower (low) and upper (high) boundaries of the array segment being considered.

2. A loop continues as long as there's a segment of the list to be considered, i.e., low is less than or equal to high.

3. The middle index of the segment is calculated.

4. The value at this middle index is compared to the target value.

5. If they match, the index is returned.

6. If the target value is greater than the middle value, the search continues with the right half of the list by adjusting the low boundary.

7. If the target value is smaller than the middle value, the search continues with the left half of the list by adjusting the high boundary.

8. The process continues until either the value is found or the segment size becomes zero (i.e., low exceeds high).

Binary Search has a time complexity of O(log n), which makes it much faster than Linear Search for large datasets, but it requires the list to be sorted.