Searching: Linear Search and Binary Search

Searching: Linear Search and Binary Search

Searching is one of the fundamental operations performed on a data structure. Searching means finding whether a particular element, called the key, is present in a collection of elements and, if present, determining its position.

For example, if an array contains:

10, 25, 30, 45, 60

and the key is 45, the searching operation determines that 45 is present at index 3.

The two basic searching techniques are:

Linear Search
Binary Search

1. Linear Search

Definition

Linear Search, also called Sequential Search, is the simplest searching technique. In this method, each element of the array is compared sequentially with the key until:

the required element is found, or
the entire array has been examined.

It does not require the array to be sorted.

Example

Consider:

A = {10, 25, 30, 45, 60}

Suppose the key is 45.

The search proceeds as:

10 → 25 → 30 → 45

↑

Found

The key is found at index 3.

Algorithm for Linear Search

Algorithm LinearSearch(A, n, key)

1. Start

2. For i = 0 to n-1

If A[i] == key

Return i

3. Return -1

4. Stop

Here:

A = array
n = number of elements
key = element to be searched
i = index of the current element
-1 indicates that the element is not found.

C Program: Linear Search

#include <stdio.h>

int main()

{

int a[100], n, key, i, found = 0;

printf("Enter number of elements: ");

scanf("%d", &n);

printf("Enter elements:\n");

for(i = 0; i < n; i++)

scanf("%d", &a[i]);

printf("Enter element to search: ");

scanf("%d", &key);

for(i = 0; i < n; i++)

{

if(a[i] == key)

{

printf("Element found at index %d\n", i);

found = 1;

break;

}

if(found == 0)

printf("Element not found\n");

return 0;

}

Working

If the input is:

Array = 12 25 37 48 59

Key = 37

The comparisons are:

12 == 37 → No

25 == 37 → No

37 == 37 → Yes

Therefore, the element is found at index 2.

2. Complexity Analysis of Linear Search

Suppose there are n elements.

Best Case

The key is present at the first position.

Only one comparison is required.

Worst Case

The key is:

present at the last position, or
not present in the array.

Therefore, approximately n comparisons are required.

Average Case

On average, approximately n/2 elements are examined.

Although the number of comparisons is approximately n/2, constants are ignored in asymptotic analysis.

Space Complexity

Linear search requires only a constant amount of additional memory.

3. Binary Search

Definition

Binary Search is an efficient searching technique that repeatedly divides a sorted array into two halves.

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

The basic principle is:

Compare the key with the middle element and eliminate the half in which the key cannot exist.

Example

Consider the sorted array:

A = {10, 20, 30, 40, 50, 60, 70}

Search key:

Initially:

10 20 30 40 50 60 70

↑

Middle

Middle element = 40

Since:

60 > 40

the left half can be discarded.

Remaining portion:

50 60 70

↑

Middle

Middle element = 60

Therefore:

60 == 60

Element found.

4. Algorithm for Binary Search

Algorithm BinarySearch(A, n, key)

1. Start

2. Set low = 0

3. Set high = n - 1

4. Repeat while low <= high

mid = (low + high) / 2

If A[mid] == key

Return mid

Else if key < A[mid]

high = mid - 1

Else

low = mid + 1

5. Return -1

6. Stop

Important Variables

Variable	Meaning
low	Starting index of current search range
high	Ending index of current search range
mid	Middle index
key	Element being searched

5. C Program: Binary Search

#include <stdio.h>

int main()

{

int a[100], n, key;

int low, high, mid;

int found = 0;

printf("Enter number of elements: ");

scanf("%d", &n);

printf("Enter elements in sorted order:\n");

for(int i = 0; i < n; i++)

scanf("%d", &a[i]);

printf("Enter element to search: ");

scanf("%d", &key);

low = 0;

high = n - 1;

while(low <= high)

{

mid = low + (high - low) / 2;

if(a[mid] == key)

{

printf("Element found at index %d\n", mid);

found = 1;

break;

}

else if(key < a[mid])

{

high = mid - 1;

}

else

{

low = mid + 1;

}

if(found == 0)

printf("Element not found\n");

return 0;

}

Why use

mid = low + (high - low) / 2;

instead of:

mid = (low + high) / 2;

The first expression is generally preferred because it avoids integer overflow when low and high are very large.

6. Complexity Analysis of Binary Search

At every step, binary search reduces the search space approximately by half.

For n elements:

n/2

n/4

n/8

...

After k divisions:

Therefore:

Taking logarithm:

Hence, the time complexity is:

Best Case

The key is the middle element in the first comparison.

Worst Case

The search continues until the search interval becomes empty or the key is found near the end of the process.

Average Case

Space Complexity

For the iterative implementation shown above:

If binary search is implemented recursively, the recursion stack requires:

7. Linear Search vs Binary Search

Basis	Linear Search	Binary Search
Basic principle	Checks elements sequentially	Repeatedly divides the search space into two halves
Data requirement	Sorted or unsorted data	Data must be sorted
Searching method	Sequential	Divide and conquer
Best-case time	O(1)	O(1)
Average-case time	O(n)	O(log n)
Worst-case time	O(n)	O(log n)
Space complexity (iterative)	O(1)	O(1)
Implementation	Very simple	Relatively more complex
Suitable for	Small or unsorted datasets	Large sorted datasets
Random access requirement	Not necessary	Generally most suitable with random-access structures such as arrays
Sorting required	No	Yes, if data is initially unsorted
Main advantage	Simple and works on unsorted data	Much faster for large sorted datasets
Main limitation	Slow for large datasets	Cannot directly be used on unsorted data

8. Complexity Comparison

For n = 1,000,000 elements:

Linear Search

Worst case:

It may need to inspect approximately one million elements.

Binary Search

Thus, binary search can locate an element in roughly 20 iterations in the worst case, assuming the array is already sorted.

This demonstrates why binary search is highly efficient for large sorted arrays.

9. Important Examination Points

Linear Search

Also known as Sequential Search.
Checks elements one by one.
Works on sorted as well as unsorted data.
Best-case complexity: O(1).
Average-case complexity: O(n).
Worst-case complexity: O(n).
Space complexity: O(1) for the iterative implementation.

Binary Search

Requires a sorted array.
Uses the divide-and-conquer principle.
Compares the search key with the middle element.
Eliminates approximately half of the search space after every comparison.
Best-case complexity: O(1).
Average-case complexity: O(log n).
Worst-case complexity: O(log n).
Iterative space complexity: O(1).
Recursive space complexity: O(log n).

Key Formula

For binary search:

For linear search:

In short: Use Linear Search when simplicity or unsorted data is important; use Binary Search when the data is sorted and efficient searching is required.