Binary Search Algorithm in Swift

by

Binary search is an efficient algorithm for finding an item from a sorted list of items. If the items are not sorted already, we need to sort them first. Binary search works by repeatedly dividing the search interval in half. Here is the steps of Binary Search:

  1. To divide the search area into half we need to set two pointers. One is first index of the search area and another one is last index of the search area. We will get mid index by using left + (right-left)/2 formula.
  2. If the value of the search key is less than the item in the middle of the interval, we will narrow the interval to the lower half. If we set right pinter to the mid, we will get left half of the array.
  3. Otherwise, narrow it to the upper half. If we set left pinter to the mid, we will get left half of the array.
  4. Repeatedly check until the value is found or the interval is empty.

Check this image for clear understanding. For better understanding, I kept index number and items same.

There are two way we can implement Binary Search algorithm in Swift.

  1. Iterative Method
  2. Recursive Method

Here is the implementation of iterative method: 

var nums = [-1,0,3,5,9,12]
var target = 9

var left = 0
var right = nums.count - 1

while left < right {
    let mid =  left + ( right - left ) / 2
    
    if nums[mid] == target{
        print("Found target at \(mid)th index.")
        break
    } else if (nums[mid] < target){
        left = mid + 1
    } else if ( nums[mid] > target){
        right = mid - 1
    }
}
// Output: Found target at 4th index.

Binary Search implementation using recursion in Swift:

func binarySearch(_ array: [Int], key: Int, left: Int, right: Int) -> Int? {
    // Base case: key not found
    if left > right {
        return nil
    }
    
    let mid = left + (right - left) / 2
    
    if array[mid] == key {
        return mid  // Base case: key found
    } else if array[mid] < key {
        // Search in the upper half
        return binarySearch(array, key: key, left: mid + 1, right: right)
    } else {
        // Search in the lower half
        return binarySearch(array, key: key, left: left, right: mid - 1)
    }
}



// Example usage
let numbers = [-1, 0, 3, 5, 9, 12]
if let index = binarySearch(numbers, key: 9, left: 0, right: numbers.count) {
    print("Found 9 at index \(index)")
} else {
    print("9 not found in the array")
}

// Output: Found 9 at index 4

Leave a Reply