Binary Search Fast AF

Binary search is an algorithm that allows you to quickly find an element in a sorted list of items. It works by repeatedly dividing the list in half and checking which half the element is in. This process is repeated until the element is found or it is determined that the element is not present in the list.

In this tutorial, we will learn how to implement binary search in Swift and understand how it works.

Implementation:

First, let’s start by creating a function that accepts a sorted array and the element we want to search for as its arguments.

func binarySearch(array: [Int], element: Int) -> Int? {
    // code goes here
}

Next, we will initialize two variables, low and high, which will represent the lower and upper bounds of the array that we are searching in. These variables will be used to determine the middle element of the array in each iteration of the search.

func binarySearch(array: [Int], element: Int) -> Int? {
    var low = 0
    var high = array.count - 1
    
    // code goes here
}

Now, we will create a while loop that will run until low is less than or equal to high. Inside the loop, we will calculate the middle index of the array by taking the average of low and high. Then, we will check if the element at the middle index is the one we are searching for. If it is, we will return the index.

func binarySearch(array: [Int], element: Int) -> Int? {
    var low = 0
    var high = array.count - 1
    
    while low <= high {
        let mid = (low + high) / 2
        if array[mid] == element {
            return mid
        }
        
        // code goes here
    }
}

If the element at the middle index is not the one we are searching for, we need to determine which half of the array we should search in. If the element we are searching for is less than the element at the middle index, we know it must be in the left half of the array, so we update high to be the middle index - 1. If the element we are searching for is greater than the element at the middle index, we know it must be in the right half of the array, so we update low to be the middle index + 1.

func binarySearch(array: [Int], element: Int) -> Int? {
    var low = 0
    var high = array.count - 1
    
    while low <= high {
        let mid = (low + high) / 2
        if array[mid] == element {
            return mid
        }
        
        if array[mid] > element {
            high = mid - 1
        } else {
            low = mid + 1
        }
    }
}

Finally, we need to add a return statement outside of the while loop to handle the case where the element is not found in the array.

func binarySearch(array: [Int], element: Int) -> Int? {
    var low = 0
    var high = array.count - 1
    
    while low <= high {
        let mid = (low + high) / 2
        if array[mid] == element {
          return mid
        }
        if array[mid] > element {
          high = mid - 1
        } else {
          low = mid + 1
        }
    }

    return nil
}

And that’s it! Now you can use the `binarySearch` function to search for an element in a sorted array.

Here is an example of how to use the function:

let array = [1, 2, 3, 4, 5, 6, 7, 8, 9]
let element = 5

if let index = binarySearch(array: array, element: element) {
    print("Element found at index: (index)")
} else {
    print("Element not found")
}

Output:

Element found at index: 4

Explanation:

The binary search algorithm works by dividing the array in half and checking which half the element is in. In each iteration, it calculates the middle index of the array and compares the element at that index to the element we are searching for. If they are equal, the search is complete and the index is returned. If the element we are searching for is less than the element at the middle index, we know it must be in the left half of the array and we update the `high` variable to be the middle index — 1. If the element we are searching for is greater than the element at the middle index, we know it must be in the right half of the array and we update the `low` variable to be the middle index + 1. This process is repeated until the element is found or it is determined that the element is not present in the array.

Conclusion:

In this tutorial, we learned how to implement binary search in Swift and understand how it works. Binary search is an efficient way to search for an element in a sorted list of items and is often used in computer science and software development. If you want to learn more about binary search and other algorithms, you can check out the following resources:

• [Swift Algorithms Club](https://www.raywenderlich.com/10739-swift-algorithms-club-binary-search)
• [Binary Search — Wikipedia](https://en.wikipedia.org/wiki/Binary_search_algorithm)
• [Introduction to Algorithms — MIT OpenCourseWare](https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/index.htm)