Introduction to Algorithms
Searching
scorpionxdev1Updated 7/23/2026 · 17 min read · 2 viewsChapter: Searching Algorithms
1. Introduction to Searching
Searching is one of the most fundamental operations in computer science. A searching algorithm is used to determine whether a particular value exists in a collection of data. When the value is found, the algorithm may also return its position or other associated information.
For example, searching is used when:
- Finding a student using a student ID.
- Finding a contact using a phone number.
- Looking for a file on a computer.
- Checking whether a username already exists.
- Finding a product in an online store.
- Looking up a word in a dictionary.
- Searching for a particular number in an array.
The value that we want to find is commonly called the target, search key, or simply key.
Consider the following array:
10, 25, 31, 46, 52, 68, 79
Suppose the target is 46. A searching algorithm examines the array and determines that 46 is available at index 3.
Index: 0 1 2 3 4 5 6
Value: 10 25 31 46 52 68 79
↑
Target
If the target is not present, the algorithm must return a special result indicating that the search failed. In C programs, -1 is commonly returned when an element cannot be found because valid array indexes begin at 0.
The performance of a searching algorithm depends on several factors:
- The number of elements in the collection.
- Whether the data is sorted.
- The data structure being used.
- Whether additional memory is available.
- How frequently searching is performed.
- Whether data is frequently inserted or deleted.
Two basic searching algorithms are:
- Linear Search
- Binary Search
Linear search works on both sorted and unsorted data. Binary search is usually much faster, but it requires the data to be sorted.
2. Basic Searching Terminology
Before learning the algorithms, it is important to understand some common terms.
2.1 Search Key
The value that the algorithm is trying to locate.
int target = 46;
Here, 46 is the search key.
2.2 Search Space
The complete collection of elements in which the target is being searched.
int numbers[] = {10, 25, 31, 46, 52, 68, 79};
This array is the search space.
2.3 Successful Search
A search is successful when the target exists in the collection.
Target: 46
Result: Found at index 3
2.4 Unsuccessful Search
A search is unsuccessful when the target does not exist.
Target: 100
Result: Element not found
2.5 Comparison
A comparison occurs when the algorithm compares the target with an element.
if (array[i] == target)
The number of comparisons is commonly used to measure the efficiency of a searching algorithm.
2.6 Sorted Data
Data is sorted when its elements are arranged in a particular order.
Ascending order:
10, 20, 30, 40, 50
Descending order:
50, 40, 30, 20, 10
Binary search requires sorted data because it uses the ordering of the elements to eliminate large parts of the search space.
3. Linear Search
3.1 Definition
Linear search, also called sequential search, examines the elements one by one until:
- The target is found, or
- The end of the collection is reached.
It is the simplest searching algorithm.
Consider the following array:
12, 25, 8, 19, 42, 31
Suppose the target is 42.
Linear search performs the following comparisons:
12 == 42? No
25 == 42? No
8 == 42? No
19 == 42? No
42 == 42? Yes
The target is found at index 4.
Linear search does not require the array to be sorted.
3.2 Linear Search Algorithm
LINEAR-SEARCH(array, size, target)
1. For each index i from 0 to size - 1:
2. If array[i] is equal to target:
3. Return i
4. Return -1
The algorithm returns the index of the target. If the target does not exist, it returns -1.
3.3 Linear Search Implementation in C
#include <stdio.h>
int linearSearch(const int array[], int size, int target)
{
for (int i = 0; i < size; i++)
{
if (array[i] == target)
{
return i;
}
}
return -1;
}
int main(void)
{
int numbers[] = {12, 25, 8, 19, 42, 31};
int size = sizeof(numbers) / sizeof(numbers[0]);
int target = 42;
int result = linearSearch(numbers, size, target);
if (result != -1)
{
printf("%d was found at index %d.\n", target, result);
}
else
{
printf("%d was not found.\n", target);
}
return 0;
}
Output
42 was found at index 4.
3.4 Explanation of the Program
The array is declared as:
int numbers[] = {12, 25, 8, 19, 42, 31};
The number of elements is calculated using:
int size = sizeof(numbers) / sizeof(numbers[0]);
sizeof(numbers) gives the total number of bytes occupied by the array. sizeof(numbers[0]) gives the size of one element.
The linear search function receives:
const int array[]
The const keyword indicates that the function will not modify the array.
The loop examines every element:
for (int i = 0; i < size; i++)
The target is compared with the current element:
if (array[i] == target)
When a match is found, the index is returned:
return i;
If the loop finishes without finding the target, the function returns:
return -1;
3.5 Step-by-Step Example
Consider:
Array: 14, 7, 22, 36, 9
Target: 36
| Step | Index | Array Element | Comparison | Result |
|---|---|---|---|---|
| 1 | 0 | 14 | 14 == 36 | False |
| 2 | 1 | 7 | 7 == 36 | False |
| 3 | 2 | 22 | 22 == 36 | False |
| 4 | 3 | 36 | 36 == 36 | True |
The search stops after the fourth comparison.
3.6 Time Complexity of Linear Search
Let n represent the number of elements.
Best Case
The target is the first element.
Target: 12
Array: 12, 25, 8, 19, 42, 31
Only one comparison is required.
Best-case time complexity: O(1)
Worst Case
The target is the final element or does not exist.
Target: 31
Array: 12, 25, 8, 19, 42, 31
The algorithm examines every element.
Worst-case time complexity: O(n)
Average Case
On average, approximately half of the elements are examined.
Average-case time complexity: O(n)
Constants are ignored in Big-O notation. Therefore, examining approximately n / 2 elements is still represented as O(n).
Space Complexity
Linear search uses only a few variables.
Space complexity: O(1)
3.7 Linear Search with User Input
#include <stdio.h>
int linearSearch(const int array[], int size, int target)
{
for (int i = 0; i < size; i++)
{
if (array[i] == target)
{
return i;
}
}
return -1;
}
int main(void)
{
int numbers[100];
int size;
int target;
printf("Enter the number of elements: ");
if (scanf("%d", &size) != 1 || size <= 0 || size > 100)
{
printf("Invalid array size.\n");
return 1;
}
printf("Enter %d integers:\n", size);
for (int i = 0; i < size; i++)
{
if (scanf("%d", &numbers[i]) != 1)
{
printf("Invalid input.\n");
return 1;
}
}
printf("Enter the value to search for: ");
if (scanf("%d", &target) != 1)
{
printf("Invalid target value.\n");
return 1;
}
int result = linearSearch(numbers, size, target);
if (result == -1)
{
printf("%d was not found in the array.\n", target);
}
else
{
printf("%d was found at index %d.\n", target, result);
}
return 0;
}
3.8 Searching for All Occurrences
A normal linear search returns the first matching index. Sometimes, the target may occur more than once.
Consider:
4, 7, 2, 7, 9, 7
The value 7 occurs at indexes 1, 3, and 5.
#include <stdio.h>
int printAllOccurrences(const int array[], int size, int target)
{
int count = 0;
for (int i = 0; i < size; i++)
{
if (array[i] == target)
{
printf("Found at index %d\n", i);
count++;
}
}
return count;
}
int main(void)
{
int numbers[] = {4, 7, 2, 7, 9, 7};
int size = sizeof(numbers) / sizeof(numbers[0]);
int target = 7;
int count = printAllOccurrences(numbers, size, target);
if (count == 0)
{
printf("%d was not found.\n", target);
}
else
{
printf("Total occurrences: %d\n", count);
}
return 0;
}
Output
Found at index 1
Found at index 3
Found at index 5
Total occurrences: 3
3.9 Advantages of Linear Search
- Simple to understand and implement.
- Works with unsorted data.
- Requires no additional memory.
- Suitable for small collections.
- Works with arrays, linked lists, and other sequential structures.
- Does not require preprocessing.
3.10 Disadvantages of Linear Search
- Slow for large collections.
- May examine every element.
- Does not benefit greatly from sorted data.
- Repeated searches can become expensive.
- Its worst-case time complexity is
O(n).
4. Binary Search
4.1 Definition
Binary search is an efficient searching algorithm that repeatedly divides the search space into two halves.
Binary search requires the collection to be sorted.
Consider the following sorted array:
10, 20, 30, 40, 50, 60, 70
Suppose the target is 60.
The algorithm first checks the middle element:
Middle value: 40
Since 60 is greater than 40, every value to the left of 40 can be ignored.
The remaining search space is:
50, 60, 70
The algorithm checks the middle again:
Middle value: 60
The target is found.
Binary search does not inspect every element. Each comparison removes approximately half of the remaining elements.
4.2 Binary Search Requirements
Binary search normally requires:
- The data must be sorted.
- The algorithm must be able to access the middle element efficiently.
- The lower and upper boundaries of the search space must be known.
Arrays are suitable for binary search because an array element can be accessed directly using its index.
4.3 Important Variables
Binary search commonly uses three index variables:
int low;
int high;
int mid;
lowrepresents the beginning of the current search range.highrepresents the end of the current search range.midrepresents the middle index.
Initially:
low = 0;
high = size - 1;
The middle index is calculated using:
mid = low + (high - low) / 2;
This form is preferred over:
mid = (low + high) / 2;
because low + high could overflow when working with very large index values.
4.4 Binary Search Algorithm
BINARY-SEARCH(array, size, target)
1. Set low to 0.
2. Set high to size - 1.
3. While low is less than or equal to high:
4. Set mid to low + (high - low) / 2.
5. If array[mid] is equal to target:
6. Return mid.
7. If array[mid] is less than target:
8. Set low to mid + 1.
9. Otherwise:
10. Set high to mid - 1.
11. Return -1.
4.5 Iterative Binary Search in C
#include <stdio.h>
int binarySearch(const int array[], int size, int target)
{
int low = 0;
int high = size - 1;
while (low <= high)
{
int mid = low + (high - low) / 2;
if (array[mid] == target)
{
return mid;
}
if (array[mid] < target)
{
low = mid + 1;
}
else
{
high = mid - 1;
}
}
return -1;
}
int main(void)
{
int numbers[] = {10, 20, 30, 40, 50, 60, 70};
int size = sizeof(numbers) / sizeof(numbers[0]);
int target = 60;
int result = binarySearch(numbers, size, target);
if (result != -1)
{
printf("%d was found at index %d.\n", target, result);
}
else
{
printf("%d was not found.\n", target);
}
return 0;
}
Output
60 was found at index 5.
4.6 Step-by-Step Binary Search Example
Consider:
Array: 5, 12, 18, 24, 31, 46, 59, 72, 85
Target: 59
Initial values:
low = 0
high = 8
Iteration 1
mid = 0 + (8 - 0) / 2
mid = 4
array[4] = 31
Since:
59 > 31
The target must be on the right side.
low = mid + 1
low = 5
Iteration 2
low = 5
high = 8
mid = 5 + (8 - 5) / 2
mid = 6
array[6] = 59
The target is found at index 6.
| Iteration | Low | High | Mid | Middle Value | Decision |
|---|---|---|---|---|---|
| 1 | 0 | 8 | 4 | 31 | Search right half |
| 2 | 5 | 8 | 6 | 59 | Target found |
4.7 Unsuccessful Binary Search Example
Consider:
Array: 10, 20, 30, 40, 50, 60
Target: 35
Iteration 1
low = 0
high = 5
mid = 2
array[mid] = 30
Since 35 > 30:
low = 3
Iteration 2
low = 3
high = 5
mid = 4
array[mid] = 50
Since 35 < 50:
high = 3
Iteration 3
low = 3
high = 3
mid = 3
array[mid] = 40
Since 35 < 40:
high = 2
Now:
low = 3
high = 2
The condition low <= high is false, so the target does not exist.
4.8 Time Complexity of Binary Search
Binary search removes half of the remaining elements after every comparison.
For an array of n elements:
n
n / 2
n / 4
n / 8
...
1
After k divisions:
n / 2^k = 1
Therefore:
n = 2^k
Taking logarithm base 2:
k = log₂(n)
Best Case
The target is the middle element.
Best-case time complexity: O(1)
Average Case
Average-case time complexity: O(log n)
Worst Case
Worst-case time complexity: O(log n)
Space Complexity
For iterative binary search:
Space complexity: O(1)
For recursive binary search:
Space complexity: O(log n)
The recursive version uses the call stack.
4.9 Number of Binary Search Comparisons
| Number of Elements | Approximate Maximum Comparisons |
|---|---|
| 8 | 3–4 |
| 16 | 4–5 |
| 32 | 5–6 |
| 1,024 | About 10 |
| 1,000,000 | About 20 |
| 1,000,000,000 | About 30 |
This demonstrates why binary search is highly efficient for large sorted collections.
5. Recursive Binary Search
Binary search can also be written recursively.
A recursive binary search function searches one half of the array by calling itself with a smaller range.
5.1 Recursive Algorithm
RECURSIVE-BINARY-SEARCH(array, low, high, target)
1. If low is greater than high:
2. Return -1.
3. Calculate mid.
4. If array[mid] is equal to target:
5. Return mid.
6. If target is less than array[mid]:
7. Search from low to mid - 1.
8. Otherwise:
9. Search from mid + 1 to high.
5.2 Recursive Binary Search in C
#include <stdio.h>
int recursiveBinarySearch(
const int array[],
int low,
int high,
int target
)
{
if (low > high)
{
return -1;
}
int mid = low + (high - low) / 2;
if (array[mid] == target)
{
return mid;
}
if (target < array[mid])
{
return recursiveBinarySearch(array, low, mid - 1, target);
}
return recursiveBinarySearch(array, mid + 1, high, target);
}
int main(void)
{
int numbers[] = {3, 8, 15, 21, 29, 34, 47, 55};
int size = sizeof(numbers) / sizeof(numbers[0]);
int target = 29;
int result = recursiveBinarySearch(
numbers,
0,
size - 1,
target
);
if (result == -1)
{
printf("%d was not found.\n", target);
}
else
{
printf("%d was found at index %d.\n", target, result);
}
return 0;
}
5.3 Iterative vs. Recursive Binary Search
| Feature | Iterative Version | Recursive Version |
|---|---|---|
| Time complexity | O(log n) | O(log n) |
| Extra space | O(1) | O(log n) |
| Uses loop | Yes | No |
| Uses function calls | No | Yes |
| Risk of stack overhead | No | Yes |
| Usually preferred in practice | Yes | Depends on the situation |
| Easy to understand conceptually | Yes | Often yes |
The iterative version is generally more memory-efficient.
6. Linear Search vs. Binary Search
| Property | Linear Search | Binary Search |
|---|---|---|
| Data must be sorted | No | Yes |
| Best-case time | O(1) | O(1) |
| Average-case time | O(n) | O(log n) |
| Worst-case time | O(n) | O(log n) |
| Iterative extra space | O(1) | O(1) |
| Suitable for small data | Yes | Yes |
| Suitable for large sorted data | Less efficient | Highly efficient |
| Works well with linked lists | Yes | Usually no |
| Implementation difficulty | Very easy | Moderate |
| Can find all occurrences easily | Yes | Requires modification |
6.1 Example Comparison
Suppose an array contains 1,000,000 elements.
In the worst case, linear search may perform:
1,000,000 comparisons
Binary search performs approximately:
log₂(1,000,000) ≈ 20 comparisons
This is a major performance difference.
However, if the array is unsorted, it may need to be sorted before binary search can be used.
Sorting normally takes approximately:
O(n log n)
Therefore, when only one search is required, sorting the data first may not always be worthwhile. When many searches will be performed on the same data, sorting once and using binary search repeatedly can be very efficient.
7. Binary Search with User Input
The user must enter the numbers in sorted order.
#include <stdio.h>
int binarySearch(const int array[], int size, int target)
{
int low = 0;
int high = size - 1;
while (low <= high)
{
int mid = low + (high - low) / 2;
if (array[mid] == target)
{
return mid;
}
else if (array[mid] < target)
{
low = mid + 1;
}
else
{
high = mid - 1;
}
}
return -1;
}
int main(void)
{
int numbers[100];
int size;
int target;
printf("Enter the number of elements: ");
if (scanf("%d", &size) != 1 || size <= 0 || size > 100)
{
printf("Invalid array size.\n");
return 1;
}
printf("Enter %d integers in ascending order:\n", size);
for (int i = 0; i < size; i++)
{
if (scanf("%d", &numbers[i]) != 1)
{
printf("Invalid input.\n");
return 1;
}
}
printf("Enter the value to search for: ");
if (scanf("%d", &target) != 1)
{
printf("Invalid target value.\n");
return 1;
}
int result = binarySearch(numbers, size, target);
if (result == -1)
{
printf("%d was not found.\n", target);
}
else
{
printf("%d was found at index %d.\n", target, result);
}
return 0;
}
8. Binary Search in Descending Order
A normal binary search assumes ascending order. The conditions must be reversed for descending order.
Consider:
90, 75, 60, 45, 30, 15
If the middle value is greater than the target, the target is located on the right side.
#include <stdio.h>
int binarySearchDescending(
const int array[],
int size,
int target
)
{
int low = 0;
int high = size - 1;
while (low <= high)
{
int mid = low + (high - low) / 2;
if (array[mid] == target)
{
return mid;
}
if (array[mid] > target)
{
low = mid + 1;
}
else
{
high = mid - 1;
}
}
return -1;
}
int main(void)
{
int numbers[] = {90, 75, 60, 45, 30, 15};
int size = sizeof(numbers) / sizeof(numbers[0]);
int target = 30;
int result = binarySearchDescending(numbers, size, target);
if (result == -1)
{
printf("%d was not found.\n", target);
}
else
{
printf("%d was found at index %d.\n", target,
0 comments
Sign in to join the discussion.