Binary Search is a highly efficient algorithm for finding a target element in a sorted array. Unlike Linear Search, which checks each element one by one, Binary Search repeatedly divides the array in half, narrowing down the search range until the element is found or the range becomes empty. This makes it significantly faster for large datasets, with a time complexity of O(log n), compared to O(n) for Linear Search.
with hands-on learning.
get the skills and confidence to land your next move.
Understanding Binary Search is a key milestone for beginners because it introduces the concept of divide and conquer, a common strategy used in many advanced algorithms. Binary Search is widely used in real-world applications like searching in databases, autocomplete features, and any system where large sorted data needs to be accessed quickly.
Program 1: Iterative Binary Search for Integers
This program demonstrates Binary Search using a straightforward loop. It searches for an integer in a sorted array and returns its index if found.
import Foundation
func binarySearchIterative(array: [Int], target: Int) -> Int? {
var left = 0
var right = array.count - 1
while left <= right {
let mid = left + (right - left) / 2
if array[mid] == target {
return mid
} else if array[mid] < target {
left = mid + 1
} else {
right = mid - 1
}
}
return nil
}
let numbers = [3, 8, 15, 23, 42, 56]
if let index = binarySearchIterative(array: numbers, target: 23) {
print("Found 23 at index:", index)
} else {
print("23 not found")
}Using a loop, the algorithm keeps halving the search space until it finds the target or concludes it does not exist. Beginners can appreciate how updating the left and right boundaries narrows down the possibilities efficiently.
Program 2: Recursive Binary Search
This version implements Binary Search recursively. The recursion splits the array into smaller segments until the target is found.
import Foundation
func binarySearchRecursive(array: [Int], target: Int, left: Int = 0, right: Int? = nil) -> Int? {
let right = right ?? array.count - 1
if left > right { return nil }
let mid = left + (right - left) / 2
if array[mid] == target {
return mid
} else if array[mid] < target {
return binarySearchRecursive(array: array, target: target, left: mid + 1, right: right)
} else {
return binarySearchRecursive(array: array, target: target, left: left, right: mid - 1)
}
}
let numbers2 = [5, 12, 18, 25, 33, 40]
if let index = binarySearchRecursive(array: numbers2, target: 25) {
print("Found 25 at index:", index)
} else {
print("25 not found")
}Recursive Binary Search helps beginners understand how problems can be broken into smaller subproblems. Although it uses more memory than iterative solutions, it is elegant and easy to read.
Program 3: Binary Search for Strings
Binary Search works with any sorted, comparable type. This example searches for a string in a sorted array of names.
import Foundation
func binarySearchStrings(array: [String], target: String) -> Int? {
var left = 0
var right = array.count - 1
while left <= right {
let mid = left + (right - left) / 2
if array[mid] == target {
return mid
} else if array[mid] < target {
left = mid + 1
} else {
right = mid - 1
}
}
return nil
}
let names = ["Alice", "Bob", "Charlie", "Diana"]
if let index = binarySearchStrings(array: names, target: "Charlie") {
print("Found Charlie at index:", index)
} else {
print("Charlie not found")
}Using Binary Search for strings shows beginners that the same algorithm can handle different types of sorted data, not just numbers, as long as the type supports comparison.
Program 4: Binary Search with Tuples Using a Key
This example demonstrates searching in an array of tuples, allowing search by a specific property, like a score or ID.
import Foundation
func binarySearchTuples(array: [(String, Int)], target: Int) -> Int? {
var left = 0
var right = array.count - 1
while left <= right {
let mid = left + (right - left) / 2
if array[mid].1 == target {
return mid
} else if array[mid].1 < target {
left = mid + 1
} else {
right = mid - 1
}
}
return nil
}
let students = [("Alice", 70), ("Bob", 85), ("Charlie", 92)]
if let index = binarySearchTuples(array: students, target: 85) {
print("Found student with score 85 at index:", index)
} else {
print("Score 85 not found")
}Binary Search on tuples teaches how the algorithm can adapt to more complex data structures by using a key for comparison, making it practical for real-world applications.
Program 5: Generic Binary Search Using Comparable
This program demonstrates a fully generic Binary Search function in Swift, which works for any type that conforms to Comparable.
import Foundation
func binarySearchGeneric<T: Comparable>(array: [T], target: T) -> Int? {
var left = 0
var right = array.count - 1
while left <= right {
let mid = left + (right - left) / 2
if array[mid] == target {
return mid
} else if array[mid] < target {
left = mid + 1
} else {
right = mid - 1
}
}
return nil
}
let numbers3: [Double] = [1.1, 2.3, 3.5, 4.7, 5.9]
if let index = binarySearchGeneric(array: numbers3, target: 3.5) {
print("Found 3.5 at index:", index)
} else {
print("3.5 not found")
}This generic function is powerful because it allows Binary Search to work for integers, floating-point numbers, strings, or any type that can be compared. Beginners can learn how generics make algorithms reusable without rewriting the core logic.
Frequently Asked Questions (FAQ)
Binary Search raises a few common questions for beginners.
Q1: Does the array need to be sorted?
Yes, Binary Search only works on sorted arrays. Sorting first is essential.
Q2: Which is faster: Linear Search or Binary Search?
Binary Search is much faster for large datasets because it reduces the search space logarithmically.
Q3: Can Binary Search be used with strings?
Yes, as long as the strings are sorted and comparable.
Q4: Can Binary Search be recursive?
Yes, recursion is a natural approach for Binary Search, though iterative solutions are often more memory-efficient.
Q5: How do I handle custom objects?
Use a key or make your object conform to Comparable. This allows the algorithm to compare and locate the target correctly.
Conclusion
Binary Search is a core algorithm in programming that introduces efficiency through divide and conquer. By practicing with integers, strings, tuples, and generic types, beginners can quickly understand its power and flexibility. Learning Binary Search lays a foundation for more advanced search and sorting algorithms, and mastering it improves both problem-solving skills and understanding of algorithm design in Swift.
