Linear and Binary Search Algorithms

Searching is the process of finding a specific value in a collection of data, such as an array. Two common search algorithms are linear search and binary search.

Both algorithms look for a target value, but they do so in different ways. Choosing the right algorithm depends on how the data is organized.

Linear Search

A linear search checks each element one at a time, starting at the beginning of the array.

If the current element matches the target value, the search stops. Otherwise, the algorithm continues to the next element until it finds the target or reaches the end of the array.

For example, suppose you want to find the value 18.

A linear search checks the values in this order:

1. Check 12.
2. Check 7.
3. Check 18. The value is found.

Because linear search examines one element at a time, it works with any array, whether the values are sorted or not.

When to Use Linear Search

Linear search is a good choice when:

• the array is small
• the data is not sorted
• simplicity is more important than speed

Binary Search

A binary search repeatedly divides the search area in half until it finds the target value or determines that it is not present.

Unlike linear search, binary search requires the array to be sorted.

For example, suppose you want to find the value 18.

A binary search works like this:

1. Check the middle value (18).
2. The middle value matches the target.
3. The search is complete.

Suppose you want to find 25 instead.

The search proceeds as follows:

1. Check the middle value (18).
2. Since 25 is greater than 18, ignore the left half of the array.
3. Check the middle of the remaining values: 21, 25, 30.
4. Find 25.

Instead of checking every element, binary search eliminates half of the remaining values after each comparison.

When to Use Binary Search

Binary search is a good choice when:

• the array is sorted
• the collection is large
• fast searches are important

Comparing the Algorithms

Linear Search	Binary Search
Checks one element at a time.	Repeatedly divides the search area in half.
Works with sorted or unsorted arrays.	Requires a sorted array.
Simple to implement.	More efficient for large sorted arrays.
May examine every element.	Usually examines far fewer elements.

Suppose an array contains 1,000 elements.

A linear search may need to examine all 1,000 elements before finding the target.

A binary search cuts the remaining search area in half after each comparison. As a result, it may find the same value after examining only about 10 elements.

For small arrays, the difference may not be noticeable. For large sorted arrays, binary search is often much faster than linear search.