Binary Search

Binary Search

Binary Search is a searching algorithm for finding an element's position in a sorted array.

Binary Search is a fundamental algorithm used to efficiently search for a target value in a sorted array. It reduces the time complexity to O(log n) by halving the search space at each step.

Binary Search Program Swift

✅ Binary Search in Swift (Iterative Version)

func binarySearch(_ nums: [Int], _ target: Int) -> Int {
    var left = 0
    var right = nums.count - 1

    while left <= right {
        let mid = left + (right - left) / 2

        if nums[mid] == target {
            return mid
        } else if nums[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }

    return -1  // target not found
}

**🧪 Example Usage**

let array = [1, 3, 5, 7, 9, 12]
let target = 7
let result = binarySearch(array, target)

print("Index of \(target): \(result)") // Output: 3

✅ Binary Search in Swift (Recursive Version)

func binarySearchRecursive(_ nums: [Int], _ target: Int, _ left: Int, _ right: Int) -> Int {
    if left > right {
        return -1
    }

    let mid = left + (right - left) / 2

    if nums[mid] == target {
        return mid
    } else if nums[mid] < target {
        return binarySearchRecursive(nums, target, mid + 1, right)
    } else {
        return binarySearchRecursive(nums, target, left, mid - 1)
    }
}

📌 Binary Search Use Cases:

Search in sorted arrays
Find floor/ceiling of a value
Search in rotated arrays
Search boundaries (first/last occurrence)
Solving problems like:
Peak element
Koko Eating Bananas
Minimum in Rotated Sorted Array

func binarySearch(_ nums: [Int], target: Int) -> Int {
    var left = 0
    var right = nums.count - 1

    while left <= right {
        let mid = left + (right - left) / 2
        if nums[mid] == target {
            return mid
        } else if nums[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return -1
}

// Example
let sortedArray = [0, 2, 6, 7, 9]
let targetElement = 6
let index = binarySearch(sortedArray, target: targetElement)
print("Element \(targetElement) found at index \(index)")

📌 Find First and Last Position of Element in Sorted Array

📝 Problem Statement

Given a sorted array of integers nums and a target value target,
return the starting and ending position of target in the array.

If the target is not found, return [-1, -1].

✅ Optimal Solution (Binary Search)

We’ll use two binary searches:

One to find the first occurrence
One to find the last occurrence

func searchRange(_ nums: [Int], _ target: Int) -> [Int] {
    func findBound(_ findFirst: Bool) -> Int {
        var left = 0, right = nums.count - 1
        var index = -1

        while left <= right {
            let mid = left + (right - left) / 2

            if nums[mid] == target {
                index = mid
                if findFirst {
                    right = mid - 1  // search on left side
                } else {
                    left = mid + 1   // search on right side
                }
            } else if nums[mid] < target {
                left = mid + 1
            } else {
                right = mid - 1
            }
        }

        return index
    }

    let first = findBound(true)
    let last = findBound(false)
    return [first, last]
}

🧪 Example Usage

let nums = [5,7,7,8,8,10]
let target = 8
let result = searchRange(nums, target)
print(result) // Output: [3, 4]

⏱️ Time & Space Complexity

Metric	Value
Time	O(log n)
Space	O(1)