Binary Search is a fundamental searching algorithm that is both efficient and widely used in programming. Unlike Linear Search, which checks each element one by one, Binary Search works on sorted data and repeatedly divides the search range in half. This “divide and conquer” approach makes it much faster for large datasets, reducing the number of comparisons needed to find a target element.
with hands-on learning.
get the skills and confidence to land your next move.
Understanding Binary Search in Rust is an excellent way for beginners to learn about recursion, loops, and efficient algorithm design. It’s used in many practical applications, such as looking up items in databases, finding elements in arrays, or implementing high-performance libraries. Learning it also provides a foundation for more advanced search algorithms and problem-solving strategies.
Program 1: Iterative Binary Search on Integers
This program demonstrates Binary Search using a simple iterative approach. It searches for a target integer in a sorted array.
fn binary_search_iterative(arr: &[i32], target: i32) -> Option<usize> {
let mut low = 0;
let mut high = arr.len() - 1;
while low <= high {
let mid = low + (high - low) / 2;
if arr[mid] == target {
return Some(mid);
} else if arr[mid] < target {
low = mid + 1;
} else {
if mid == 0 { break; } // prevent underflow
high = mid - 1;
}
}
None
}
fn main() {
let numbers = [5, 10, 15, 20, 25, 30];
let target = 20;
println!("Array: {:?}", numbers);
match binary_search_iterative(&numbers, target) {
Some(idx) => println!("Element {} found at index {}", target, idx),
None => println!("Element {} not found", target),
}
}In this program, the array is split in half repeatedly, and the search range is adjusted based on comparisons. Iterative Binary Search avoids recursion, making it memory-efficient for large arrays.
Program 2: Recursive Binary Search
Here, Binary Search is implemented recursively, which is an elegant approach and helps beginners understand how function calls can manage iterations.
fn binary_search_recursive(arr: &[i32], target: i32, low: usize, high: usize) -> Option<usize> {
if low > high {
return None;
}
let mid = low + (high - low) / 2;
if arr[mid] == target {
return Some(mid);
} else if arr[mid] < target {
return binary_search_recursive(arr, target, mid + 1, high);
} else {
if mid == 0 { return None; } // prevent underflow
return binary_search_recursive(arr, target, low, mid - 1);
}
}
fn main() {
let numbers = [1, 3, 5, 7, 9, 11];
let target = 7;
println!("Array: {:?}", numbers);
match binary_search_recursive(&numbers, target, 0, numbers.len() - 1) {
Some(idx) => println!("Element {} found at index {}", target, idx),
None => println!("Element {} not found", target),
}
}Recursive Binary Search highlights how an algorithm can call itself to reduce a problem size step by step. Beginners can see how the search range shrinks naturally without explicit loops.
Program 3: Binary Search on Floating-Point Numbers
Binary Search can also work on sorted arrays of floating-point numbers. This example shows how to implement it safely with floats.
fn binary_search_floats(arr: &[f64], target: f64) -> Option<usize> {
let mut low = 0;
let mut high = arr.len() - 1;
while low <= high {
let mid = low + (high - low) / 2;
if (arr[mid] - target).abs() < std::f64::EPSILON {
return Some(mid);
} else if arr[mid] < target {
low = mid + 1;
} else {
if mid == 0 { break; }
high = mid - 1;
}
}
None
}
fn main() {
let numbers = [1.1, 2.5, 3.8, 4.9, 5.2];
let target = 3.8;
println!("Array: {:?}", numbers);
match binary_search_floats(&numbers, target) {
Some(idx) => println!("Element {} found at index {}", target, idx),
None => println!("Element {} not found", target),
}
}This program demonstrates precision handling with floating-point numbers, which is important for beginners working with decimals in Rust.
Program 4: Binary Search on Strings
Binary Search can be applied to sorted arrays of strings. This example finds a word in a sorted list.
fn binary_search_string(arr: &[&str], target: &str) -> Option<usize> {
let mut low = 0;
let mut high = arr.len() - 1;
while low <= high {
let mid = low + (high - low) / 2;
if arr[mid] == target {
return Some(mid);
} else if arr[mid] < target {
low = mid + 1;
} else {
if mid == 0 { break; }
high = mid - 1;
}
}
None
}
fn main() {
let words = ["apple", "banana", "cherry", "date", "fig"];
let target = "cherry";
println!("Array: {:?}", words);
match binary_search_string(&words, target) {
Some(idx) => println!("Word '{}' found at index {}", target, idx),
None => println!("Word '{}' not found", target),
}
}This example shows that Binary Search isn’t limited to numbers; it works for any type that can be compared. Beginners can see how Rust handles string comparisons in a sorted array.
Program 5: Binary Search with Debug Output
Adding debug output helps beginners visualize each comparison and understand how Binary Search reduces the search range.
fn binary_search_debug(arr: &[i32], target: i32) -> Option<usize> {
let mut low = 0;
let mut high = arr.len() - 1;
while low <= high {
let mid = low + (high - low) / 2;
println!("Checking index {}: value {}", mid, arr[mid]);
if arr[mid] == target {
return Some(mid);
} else if arr[mid] < target {
low = mid + 1;
} else {
if mid == 0 { break; }
high = mid - 1;
}
}
None
}
fn main() {
let numbers = [2, 4, 6, 8, 10];
let target = 6;
println!("Array: {:?}", numbers);
match binary_search_debug(&numbers, target) {
Some(idx) => println!("Element {} found at index {}", target, idx),
None => println!("Element {} not found", target),
}
}Debug output helps learners follow the algorithm’s decision-making process and understand why the search range changes with each step.
Frequently Asked Questions (FAQ)
Q1: What is the time complexity of Binary Search?
Binary Search has a time complexity of O(log n), which is much faster than Linear Search for large sorted datasets.
Q2: Can Binary Search work on unsorted arrays?
No, the array must be sorted for Binary Search to work correctly.
Q3: What is the difference between iterative and recursive Binary Search?
Iterative uses loops and is memory-efficient, while recursive calls itself and is elegant but may use more stack memory for large arrays.
Q4: Can Binary Search be used on strings or floating-point numbers?
Yes, it can be applied to any comparable type, including strings and floats.
Q5: Why learn Binary Search?
Binary Search teaches efficient search strategies, recursion, and algorithm design, which are critical skills for Rust programmers and general problem-solving.
Conclusion
Binary Search is a powerful, efficient algorithm for searching in sorted arrays. By learning iterative and recursive approaches, beginners in Rust can understand loops, recursion, and data comparisons. Implementing Binary Search on integers, floats, and strings builds confidence in applying the algorithm to practical problems. Practicing it helps learners grasp efficient searching and prepares them for more advanced algorithms.
