Searching is one of the most important tasks in programming, especially when dealing with large datasets. While Linear Search checks each element one by one, Binary Search is much faster because it uses a sorted array and repeatedly divides the search space in half. This approach makes it efficient and widely used in many applications like looking up a number in a phonebook, finding records in a database, or checking for a specific item in a sorted list.
with hands-on learning.
get the skills and confidence to land your next move.
Binary Search is a key concept for beginners because it introduces ideas like recursion, loops, and the importance of sorted data. By understanding Binary Search, you not only learn a practical algorithm but also get familiar with problem-solving strategies that are used in more advanced algorithms, such as search trees or divide-and-conquer techniques.
Program 1: Binary Search Using a Loop
This program demonstrates Binary Search using a simple while-loop. It repeatedly checks the middle element of the array and narrows down the search range until it finds the target.
open System
let binarySearch (arr:int[]) key =
let mutable left = 0
let mutable right = arr.Length - 1
let mutable foundIndex = -1
while left <= right do
let mid = left + (right - left) / 2
if arr.[mid] = key then
foundIndex <- mid
left <- right + 1 // exit loop
elif arr.[mid] < key then
left <- mid + 1
else
right <- mid - 1
foundIndex
[<EntryPoint>]
let main argv =
let numbers = [| 1; 3; 5; 7; 9; 11 |]
let key = 7
let result = binarySearch numbers key
if result <> -1 then
printfn "Element %d found at index %d" key result
else
printfn "Element %d not found" key
0In this program, the array is assumed to be sorted. The search range is repeatedly reduced by comparing the key with the middle element. This makes Binary Search much faster than Linear Search for large arrays, as it eliminates half of the remaining elements each time.
Program 2: Recursive Binary Search
Recursion is a natural fit for Binary Search because the problem can be divided into smaller sub-problems. This program demonstrates a recursive implementation of Binary Search in F#.
open System
let rec binarySearchRec (arr:int[]) key left right =
if left > right then -1
else
let mid = left + (right - left) / 2
if arr.[mid] = key then mid
elif arr.[mid] < key then binarySearchRec arr key (mid + 1) right
else binarySearchRec arr key left (mid - 1)
[<EntryPoint>]
let main argv =
let numbers = [| 2; 4; 6; 8; 10; 12 |]
let key = 10
let result = binarySearchRec numbers key 0 (numbers.Length - 1)
if result <> -1 then
printfn "Element %d found at index %d" key result
else
printfn "Element %d not found" key
0The recursive approach works by calling the function on the left or right half of the array depending on the comparison result. Beginners can learn how recursion simplifies problems by focusing on smaller subsets of the data.
Program 3: Binary Search for Strings
Binary Search can also work on strings or any comparable type. This program searches for a name in a sorted list of strings.
open System
let rec binarySearchString (arr:string[]) key left right =
if left > right then None
else
let mid = left + (right - left) / 2
if arr.[mid] = key then Some mid
elif arr.[mid] < key then binarySearchString arr key (mid + 1) right
else binarySearchString arr key left (mid - 1)
[<EntryPoint>]
let main argv =
let names = [| "Albus"; "Harry"; "Hermione"; "Ron"; "Sirius" |]
Array.sortInPlace names
let key = "Hermione"
match binarySearchString names key 0 (names.Length - 1) with
| Some index -> printfn "Name '%s' found at index %d" key index
| None -> printfn "Name '%s' not found" key
0This example demonstrates that Binary Search is versatile. Sorting is required first, but once sorted, the algorithm can efficiently find the desired string. Beginners see how the same logic for numbers applies to other types.
Program 4: Binary Search Returning Option Type
Using F#’s option type makes the result safer and more idiomatic than returning -1. This program returns Some index if the element is found and None if it is not.
open System
let rec binarySearchOption (arr:int[]) key left right =
if left > right then None
else
let mid = left + (right - left) / 2
if arr.[mid] = key then Some mid
elif arr.[mid] < key then binarySearchOption arr key (mid + 1) right
else binarySearchOption arr key left (mid - 1)
[<EntryPoint>]
let main argv =
let numbers = [| 1; 2; 3; 4; 5; 6 |]
let key = 5
match binarySearchOption numbers key 0 (numbers.Length - 1) with
| Some index -> printfn "Element %d found at index %d" key index
| None -> printfn "Element %d not found" key
0This approach helps beginners understand safe handling of search results without relying on magic numbers like -1. It also fits well with F#’s functional programming style.
Program 5: Binary Search on Negative and Positive Numbers
Binary Search works perfectly with both negative and positive numbers as long as the array is sorted. This program shows a mixed array search.
open System
let rec binarySearchMixed (arr:int[]) key left right =
if left > right then -1
else
let mid = left + (right - left) / 2
if arr.[mid] = key then mid
elif arr.[mid] < key then binarySearchMixed arr key (mid + 1) right
else binarySearchMixed arr key left (mid - 1)
[<EntryPoint>]
let main argv =
let numbers = [| -10; -3; 0; 4; 7; 12 |]
let key = -3
let result = binarySearchMixed numbers key 0 (numbers.Length - 1)
if result <> -1 then
printfn "Element %d found at index %d" key result
else
printfn "Element %d not found" key
0This example shows that Binary Search does not require any changes to handle negative values, as long as the array is sorted. Beginners can see how the same logic applies to mixed datasets.
Frequently Asked Questions (FAQ)
This section answers common beginner questions about Binary Search.
Q1. What is Binary Search?
Binary Search is an efficient searching algorithm that works on sorted arrays by repeatedly dividing the search space in half.
Q2. Does Binary Search work on unsorted arrays?
No, the array must be sorted before using Binary Search, otherwise the results may be incorrect.
Q3. What is the time complexity of Binary Search?
The time complexity is O(log n) in both average and worst cases, which is much faster than Linear Search for large arrays.
Q4. Can Binary Search handle negative numbers?
Yes, it works for negative, zero, and positive numbers as long as the array is sorted.
Q5. Should beginners learn Binary Search?
Yes, Binary Search is a fundamental algorithm that teaches efficient searching techniques and lays the foundation for advanced algorithms.
Conclusion
Binary Search is a powerful and efficient search algorithm that every beginner should learn. Through multiple F# programs, we explored iterative and recursive implementations, handling numbers, strings, negative numbers, and using F#’s option type for safer results.
By practicing these examples, beginners can understand how dividing a problem into smaller parts makes algorithms more efficient, how sorted data is crucial for certain operations, and how recursion and loops can be used to implement practical searching solutions in F#.
