Searching is one of the most common tasks in programming. Whether you are looking for a number in an array, a word in a list, or a record in a database, knowing how to find an item efficiently is essential. Linear Search is the simplest search algorithm and is perfect for beginners to start with because it is easy to understand and implement.
with hands-on learning.
get the skills and confidence to land your next move.
Linear Search works by checking each element of a collection one by one until it finds the target value. While it may not be the fastest for large datasets compared to binary search, it is very versatile because it does not require the collection to be sorted. This makes Linear Search useful in many real-world situations, such as searching through unsorted lists of names, product codes, or numbers.
Program 1: Basic Linear Search Using a Loop
This program demonstrates the simplest way to implement Linear Search using a loop. It goes through each element in an array to check if it matches the search key.
open System
let linearSearch (arr : int[]) key =
let rec search i =
if i >= arr.Length then -1
elif arr.[i] = key then i
else search (i + 1)
search 0
[<EntryPoint>]
let main argv =
let numbers = [| 5; 3; 8; 1; 9; 2 |]
let key = 8
let result = linearSearch 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, we use a mutable variable to track the index where the key is found. The loop checks each element one by one. If a match is found, the index is returned; otherwise, -1 indicates that the key is not present. This approach is straightforward and easy for beginners to grasp.
Program 2: Linear Search Using Recursion
Recursion is a powerful concept in functional programming. This program shows how Linear Search can be implemented recursively, which is common in F#.
open System
let rec linearSearchRec (arr:int[]) key index =
if index >= arr.Length then -1
elif arr.[index] = key then index
else linearSearchRec arr key (index + 1)
[<EntryPoint>]
let main argv =
let numbers = [| 10; 4; 6; 2; 9 |]
let key = 6
let result = linearSearchRec numbers key 0
if result <> -1 then
printfn "Element %d found at index %d" key result
else
printfn "Element %d not found" key
0Here, the function checks the current index, and if the key is not found, it calls itself with the next index. Recursion allows beginners to see how problems can be solved by breaking them into smaller, repeated tasks.
Program 3: Linear Search for Strings
Linear Search can be applied to any comparable type. This program searches for a string in a list of names.
open System
let linearSearchString (arr : string[]) key =
let rec search i =
if i >= arr.Length then -1
elif arr.[i] = key then i
else search (i + 1)
search 0
[<EntryPoint>]
let main argv =
let names = [| "Harry"; "Hermione"; "Ron"; "Sirius" |]
let key = "Ron"
let result = linearSearchString names key
if result <> -1 then
printfn "Name '%s' found at index %d" key result
else
printfn "Name '%s' not found" key
0This demonstrates that Linear Search is not limited to numbers. Beginners can see how the same logic applies to strings or other types, making it a versatile tool.
Program 4: Linear Search Using Option Type
In F#, we can use the option type to represent the result more safely instead of using -1. This program returns Some index if the element is found and None otherwise.
open System
let linearSearchOption (arr : int[]) key =
let rec search i =
if i >= arr.Length then None
elif arr.[i] = key then Some i
else search (i + 1)
search 0
[<EntryPoint>]
let main argv =
let numbers = [| 7; 1; 4; 9; 3 |]
let key = 4
match linearSearchOption numbers key with
| Some index -> printfn "Element %d found at index %d" key index
| None -> printfn "Element %d not found" key
0Using option makes the program safer and more idiomatic in F#. Beginners learn to handle search results without relying on sentinel values like -1.
Program 5: Linear Search for Negative and Positive Numbers
Linear Search works the same for negative and positive numbers. This program demonstrates searching in a mixed array of integers.
open System
let linearSearchMixed (arr : int[]) key =
let rec search i =
if i >= arr.Length then -1
elif arr.[i] = key then i
else search (i + 1)
search 0
[<EntryPoint>]
let main argv =
let numbers = [| -5; 3; -1; 7; -2; 0 |]
let key = -2
let result = linearSearchMixed numbers key
if result <> -1 then
printfn "Element %d found at index %d" key result
else
printfn "Element %d not found" key
0This shows that Linear Search does not need any adjustments for negative values. It is a simple, reliable way to find elements in any array.
Frequently Asked Questions (FAQ)
This section answers common beginner questions about Linear Search.
Q1. What is Linear Search?
Linear Search is a simple method to find an element by checking each item in the collection one by one until a match is found.
Q2. Does Linear Search require sorted data?
No, Linear Search works with unsorted or sorted data, which makes it very flexible.
Q3. What is the time complexity of Linear Search?
The average and worst-case time complexity is O(n), where n is the number of elements in the array.
Q4. Can Linear Search handle negative numbers?
Yes, Linear Search works the same way for negative numbers, zero, and positive numbers.
Q5. Should beginners learn Linear Search?
Yes, it is a fundamental algorithm that teaches iteration, recursion, and basic searching concepts, forming the foundation for more advanced searches.
Conclusion
Linear Search is a simple yet essential algorithm for beginners. It is easy to understand, works with any type of data, and can be implemented using loops, recursion, or functional approaches in F#. Through multiple programs, we explored searching for numbers, strings, negative numbers, and even using F#’s option type for safer results.
Practicing Linear Search helps beginners develop a strong understanding of searching techniques, iteration, and recursion, preparing them for more advanced algorithms in the future.
