Chapter 3: Searching Algorithms

Introduction

Searching is one of the most fundamental operations in computer science. Every time you search for a file, look up a contact, or find a product online, you're using a searching algorithm. Understanding different search techniques and their performance characteristics is essential for building efficient software.

Why This Matters

Searching appears everywhere:

Database queries finding records
Web browsers finding text on a page
Operating systems locating files
Games finding players or objects
Applications validating user input

The difference between O(n) and O(log n) search can mean:

Milliseconds vs. seconds for large datasets
Responsive vs. sluggish user interfaces
Scalable vs. non-scalable systems
Feasible vs. impossible operations on huge data

How to Study This Chapter

Implement each algorithm - Don't just read; code them yourself
Visualize the process - Draw how each search progresses
Compare performance - Time algorithms with different input sizes
Understand prerequisites - Some algorithms require sorted data
Practice problem variations - Adapt algorithms to solve related problems

Linear Search

Linear search (sequential search) checks each element one by one until finding the target or reaching the end.

Algorithm

1. Start from the first element
2. Compare current element with target
3. If match found, return index
4. Move to next element
5. Repeat until found or end reached
6. Return -1 if not found

C Implementation

#include <stdio.h>

int linearSearch(int arr[], int size, int target) { for (int i = 0; i < size; i++) { if (arr[i] == target) { return i; } } return -1; }

int main() { int arr[] = {64, 25, 12, 22, 11, 45, 78, 34}; int size = 8; int target = 22;

int result = linearSearch(arr, size, target);

if (result != -1) {
    printf("Element found at index %d\n", result);
} else {
    printf("Element not found\n");
}

return 0;

}

C++ Implementation

#include <iostream>
#include <vector>
using namespace std;

int linearSearch(const vector& arr, int target) { for (size_t i = 0; i < arr.size(); i++) { if (arr[i] == target) { return i; } } return -1; }

int main() { vector arr = {64, 25, 12, 22, 11, 45, 78, 34}; int target = 22;

int result = linearSearch(arr, target);

if (result != -1) {
    cout << "Element found at index " << result << endl;
} else {
    cout << "Element not found" << endl;
}

return 0;

}

Java Implementation

public class LinearSearch {
    public static int linearSearch(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) {
                return i;
            }
        }
        return -1;
    }

public static void main(String[] args) {
    int[] arr = {64, 25, 12, 22, 11, 45, 78, 34};
    int target = 22;

    int result = linearSearch(arr, target);

    if (result != -1) {
        System.out.println("Element found at index " + result);
    } else {
        System.out.println("Element not found");
    }
}

}

Complexity Analysis

Time Complexity:
- Best case: O(1) - element is first
- Average case: O(n) - element in middle
- Worst case: O(n) - element is last or not present
Space Complexity: O(1)

When to Use

Unsorted data - only option for unsorted arrays
Small datasets - overhead of sorting not worth it
Single search - if searching once, sorting first is wasteful
Linked lists - can't use binary search efficiently

Binary Search

Binary search efficiently finds elements in sorted arrays by repeatedly dividing the search interval in half.

Algorithm

1. Set left = 0, right = size - 1
2. While left <= right:
   a. Calculate mid = (left + right) / 2
   b. If arr[mid] == target, return mid
   c. If arr[mid] < target, search right half (left = mid + 1)
   d. If arr[mid] > target, search left half (right = mid - 1)
3. Return -1 if not found

Visualization

Array: [2, 5, 8, 12, 16, 23, 38, 45, 56, 67, 78]
Target: 23

Step 1: [2, 5, 8, 12, 16, |23|, 38, 45, 56, 67, 78] L M R mid = 23 ✓ Found!

Target: 45

Step 1: [2, 5, 8, 12, 16, |23|, 38, 45, 56, 67, 78] L M R 23 < 45, search right →

Step 2: [2, 5, 8, 12, 16, 23, 38, |45|, 56, 67, 78] L M R mid = 45 ✓ Found!

C Implementation (Iterative)

#include <stdio.h>

int binarySearch(int arr[], int size, int target) { int left = 0; int right = size - 1;

while (left <= right) {
    int mid = left + (right - left) / 2;  // Prevents overflow

    if (arr[mid] == target) {
        return mid;
    }
    else if (arr[mid] < target) {
        left = mid + 1;
    }
    else {
        right = mid - 1;
    }
}

return -1;

}

int main() { int arr[] = {2, 5, 8, 12, 16, 23, 38, 45, 56, 67, 78}; int size = 11; int target = 23;

int result = binarySearch(arr, size, target);

if (result != -1) {
    printf("Element found at index %d\n", result);
} else {
    printf("Element not found\n");
}

return 0;

}

C Implementation (Recursive)

#include <stdio.h>

int binarySearchRecursive(int arr[], int left, int right, int target) { if (left > right) { return -1; }

int mid = left + (right - left) / 2;

if (arr[mid] == target) {
    return mid;
}
else if (arr[mid] < target) {
    return binarySearchRecursive(arr, mid + 1, right, target);
}
else {
    return binarySearchRecursive(arr, left, mid - 1, target);
}

}

int main() { int arr[] = {2, 5, 8, 12, 16, 23, 38, 45, 56, 67, 78}; int size = 11;

int result = binarySearchRecursive(arr, 0, size - 1, 23);

if (result != -1) {
    printf("Element found at index %d\n", result);
} else {
    printf("Element not found\n");
}

return 0;

}

C++ Implementation

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int binarySearch(const vector& arr, int target) { int left = 0; int right = arr.size() - 1;

while (left <= right) {
    int mid = left + (right - left) / 2;

    if (arr[mid] == target) {
        return mid;
    }
    else if (arr[mid] < target) {
        left = mid + 1;
    }
    else {
        right = mid - 1;
    }
}

return -1;

}

int main() { vector arr = {2, 5, 8, 12, 16, 23, 38, 45, 56, 67, 78}; int target = 23;

// Using custom implementation
int result1 = binarySearch(arr, target);

// Using STL binary_search (returns bool)
bool found = binary_search(arr.begin(), arr.end(), target);

// Using STL lower_bound (returns iterator)
auto it = lower_bound(arr.begin(), arr.end(), target);
int result2 = (it != arr.end() && *it == target) ? distance(arr.begin(), it) : -1;

cout << "Custom: " << result1 << endl;
cout << "STL found: " << found << endl;
cout << "lower_bound: " << result2 << endl;

return 0;

}

Java Implementation

import java.util.Arrays;

public class BinarySearch { public static int binarySearch(int[] arr, int target) { int left = 0; int right = arr.length - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] == target) {
            return mid;
        }
        else if (arr[mid] < target) {
            left = mid + 1;
        }
        else {
            right = mid - 1;
        }
    }

    return -1;
}

public static void main(String[] args) {
    int[] arr = {2, 5, 8, 12, 16, 23, 38, 45, 56, 67, 78};
    int target = 23;

    // Custom implementation
    int result1 = binarySearch(arr, target);

    // Using Arrays.binarySearch
    int result2 = Arrays.binarySearch(arr, target);

    System.out.println("Custom: " + result1);
    System.out.println("Arrays.binarySearch: " + result2);
}

}

Complexity Analysis

Time Complexity: O(log n)
- Each iteration halves the search space
- n = 1,000,000 → ~20 comparisons
Space Complexity:
- Iterative: O(1)
- Recursive: O(log n) for call stack
Requirement: Array must be sorted

Common Pitfall: Integer Overflow

// WRONG - can overflow for large left and right
int mid = (left + right) / 2;

// CORRECT - prevents overflow int mid = left + (right - left) / 2;

Binary Search Variations

Find First Occurrence

int findFirstOccurrence(int arr[], int size, int target) {
    int left = 0;
    int right = size - 1;
    int result = -1;

while (left <= right) {
    int mid = left + (right - left) / 2;

    if (arr[mid] == target) {
        result = mid;
        right = mid - 1;  // Continue searching left
    }
    else if (arr[mid] < target) {
        left = mid + 1;
    }
    else {
        right = mid - 1;
    }
}

return result;

}

Find Last Occurrence

int findLastOccurrence(int arr[], int size, int target) {
    int left = 0;
    int right = size - 1;
    int result = -1;

while (left <= right) {
    int mid = left + (right - left) / 2;

    if (arr[mid] == target) {
        result = mid;
        left = mid + 1;  // Continue searching right
    }
    else if (arr[mid] < target) {
        left = mid + 1;
    }
    else {
        right = mid - 1;
    }
}

return result;

}

Count Occurrences

int countOccurrences(int arr[], int size, int target) {
    int first = findFirstOccurrence(arr, size, target);
    if (first == -1) return 0;

int last = findLastOccurrence(arr, size, target);
return last - first + 1;

}

Interpolation Search

Interpolation search improves binary search for uniformly distributed sorted arrays by guessing where the target might be.

Algorithm

Instead of always checking the middle:

mid = left + ((target - arr[left]) * (right - left)) / (arr[right] - arr[left]);

C Implementation

#include <stdio.h>

int interpolationSearch(int arr[], int size, int target) { int left = 0; int right = size - 1;

while (left <= right && target >= arr[left] && target <= arr[right]) {
    if (left == right) {
        if (arr[left] == target) return left;
        return -1;
    }

    // Estimate position
    int pos = left + ((target - arr[left]) * (right - left)) /
                     (arr[right] - arr[left]);

    if (arr[pos] == target) {
        return pos;
    }
    else if (arr[pos] < target) {
        left = pos + 1;
    }
    else {
        right = pos - 1;
    }
}

return -1;

}

int main() { int arr[] = {10, 20, 30, 40, 50, 60, 70, 80, 90}; int result = interpolationSearch(arr, 9, 70); printf("Found at index: %d\n", result); return 0; }

C++ Implementation

#include <iostream>
#include <vector>
using namespace std;

int interpolationSearch(const vector& arr, int target) { int left = 0; int right = arr.size() - 1;

while (left <= right && target >= arr[left] && target <= arr[right]) {
    if (left == right) {
        return (arr[left] == target) ? left : -1;
    }

    int pos = left + ((target - arr[left]) * (right - left)) /
                     (arr[right] - arr[left]);

    if (arr[pos] == target) {
        return pos;
    }
    else if (arr[pos] < target) {
        left = pos + 1;
    }
    else {
        right = pos - 1;
    }
}

return -1;

}

int main() { vector arr = {10, 20, 30, 40, 50, 60, 70, 80, 90}; cout << "Found at index: " << interpolationSearch(arr, 70) << endl; return 0; }

Java Implementation

public class InterpolationSearch {
    public static int interpolationSearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;

    while (left <= right && target >= arr[left] && target <= arr[right]) {
        if (left == right) {
            return (arr[left] == target) ? left : -1;
        }

        int pos = left + ((target - arr[left]) * (right - left)) /
                         (arr[right] - arr[left]);

        if (arr[pos] == target) {
            return pos;
        }
        else if (arr[pos] < target) {
            left = pos + 1;
        }
        else {
            right = pos - 1;
        }
    }

    return -1;
}

public static void main(String[] args) {
    int[] arr = {10, 20, 30, 40, 50, 60, 70, 80, 90};
    System.out.println("Found at index: " + interpolationSearch(arr, 70));
}

}

Complexity Analysis

Time Complexity:
- Best case: O(log log n) for uniform distribution
- Worst case: O(n) for non-uniform distribution
Space Complexity: O(1)
Best for: Large, uniformly distributed datasets

Jump Search

Jump search jumps ahead by fixed steps, then performs linear search in the block where the element exists.

Algorithm

1. Set step = √n
2. Jump ahead by step until arr[step] >= target
3. Perform linear search in previous block

C Implementation

#include <stdio.h>
#include <math.h>

int jumpSearch(int arr[], int size, int target) { int step = sqrt(size); int prev = 0;

// Jump to find block
while (arr[(step < size ? step : size) - 1] < target) {
    prev = step;
    step += sqrt(size);
    if (prev >= size) {
        return -1;
    }
}

// Linear search in block
while (arr[prev] < target) {
    prev++;
    if (prev == (step < size ? step : size)) {
        return -1;
    }
}

if (arr[prev] == target) {
    return prev;
}

return -1;

}

int main() { int arr[] = {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377}; int result = jumpSearch(arr, 15, 55); printf("Found at index: %d\n", result); return 0; }

C++ Implementation

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int jumpSearch(const vector& arr, int target) { int n = arr.size(); int step = sqrt(n); int prev = 0;

while (arr[min(step, n) - 1] < target) {
    prev = step;
    step += sqrt(n);
    if (prev >= n) {
        return -1;
    }
}

while (arr[prev] < target) {
    prev++;
    if (prev == min(step, n)) {
        return -1;
    }
}

return (arr[prev] == target) ? prev : -1;

}

int main() { vector arr = {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377}; cout << "Found at index: " << jumpSearch(arr, 55) << endl; return 0; }

Java Implementation

public class JumpSearch {
    public static int jumpSearch(int[] arr, int target) {
        int n = arr.length;
        int step = (int) Math.sqrt(n);
        int prev = 0;

    while (arr[Math.min(step, n) - 1] < target) {
        prev = step;
        step += (int) Math.sqrt(n);
        if (prev >= n) {
            return -1;
        }
    }

    while (arr[prev] < target) {
        prev++;
        if (prev == Math.min(step, n)) {
            return -1;
        }
    }

    return (arr[prev] == target) ? prev : -1;
}

public static void main(String[] args) {
    int[] arr = {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377};
    System.out.println("Found at index: " + jumpSearch(arr, 55));
}

}

Complexity Analysis

Time Complexity: O(√n)
Space Complexity: O(1)
Advantage: Better than linear for sorted arrays, works with sequential access

Exponential Search

Exponential search finds range where element exists, then uses binary search.

C Implementation

#include <stdio.h>

int binarySearch(int arr[], int left, int right, int target);

int exponentialSearch(int arr[], int size, int target) { if (arr[0] == target) { return 0; }

int i = 1;
while (i < size && arr[i] <= target) {
    i *= 2;
}

return binarySearch(arr, i / 2, (i < size ? i : size - 1), target);

}

int binarySearch(int arr[], int left, int right, int target) { while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] == target) return mid; else if (arr[mid] < target) left = mid + 1; else right = mid - 1; } return -1; }

int main() { int arr[] = {2, 3, 4, 10, 40, 50, 60, 70, 80, 90}; printf("Found at index: %d\n", exponentialSearch(arr, 10, 70)); return 0; }

Complexity Analysis

Time Complexity: O(log n)
Space Complexity: O(1)
Best for: Unbounded/infinite arrays

Ternary Search

Ternary search divides array into three parts instead of two.

C Implementation

int ternarySearch(int arr[], int left, int right, int target) {
    if (left > right) return -1;

int mid1 = left + (right - left) / 3;
int mid2 = right - (right - left) / 3;

if (arr[mid1] == target) return mid1;
if (arr[mid2] == target) return mid2;

if (target < arr[mid1]) {
    return ternarySearch(arr, left, mid1 - 1, target);
}
else if (target > arr[mid2]) {
    return ternarySearch(arr, mid2 + 1, right, target);
}
else {
    return ternarySearch(arr, mid1 + 1, mid2 - 1, target);
}

}

Complexity Analysis

Time Complexity: O(log₃ n)
Note: Binary search is usually faster despite similar complexity (fewer comparisons per iteration)

Algorithm Comparison

Algorithm	Time (Best)	Time (Avg)	Time (Worst)	Space	Prerequisites
Linear	O(1)	O(n)	O(n)	O(1)	None
Binary	O(1)	O(log n)	O(log n)	O(1)	Sorted
Interpolation	O(1)	O(log log n)	O(n)	O(1)	Sorted, uniform
Jump	O(1)	O(√n)	O(√n)	O(1)	Sorted
Exponential	O(1)	O(log n)	O(log n)	O(1)	Sorted

Common Mistakes

Using binary search on unsorted data - Returns wrong results
Off-by-one errors - Wrong loop condition or mid calculation
Integer overflow - Using (left + right) / 2
Infinite loops - Not updating left or right correctly
Wrong comparison in interpolation - Division by zero when arr[left] == arr[right]
Not handling duplicates - Standard binary search finds any occurrence, not first/last
Forgetting edge cases - Empty array, single element, target not in range

Debugging Tips

Print loop variables - Track left, right, mid at each iteration
Test edge cases - Empty array, single element, first/last element
Verify sorted input - Binary search family requires sorted data
Check bounds - Ensure indices stay within [0, size-1]
Use assertions - Assert preconditions like arr[left] <= arr[right]
Visualize on paper - Draw array and trace algorithm steps
Test with duplicates - Ensure correct behavior with repeated elements

Mini Exercises

Implement linear search for a linked list
Find the square root of a number using binary search
Search in a rotated sorted array
Find peak element in an array
Search in a 2D sorted matrix
Find the first bad version (binary search variant)
Find minimum in a rotated sorted array
Search for a range (first and last position)
Find the closest element to a target
Implement binary search without recursion

Review Questions

Why can't binary search be used on unsorted arrays?
What's the space complexity difference between iterative and recursive binary search?
When is interpolation search better than binary search?
Why is jump search useful for linked lists compared to binary search?
How many comparisons does binary search make for 1 million elements in worst case?

Reference Checklist

By the end of this chapter, you should be able to:

Implement linear search in C, C++, and Java
Implement iterative and recursive binary search
Analyze time and space complexity of each algorithm
Find first/last occurrence using binary search
Implement interpolation and jump search
Choose appropriate search algorithm for a problem
Avoid common pitfalls like integer overflow
Handle edge cases and duplicates correctly

Next Steps

Now that you understand searching algorithms, Chapter 4 explores sorting algorithms. You'll learn bubble sort, merge sort, quicksort, and other techniques that organize data—a prerequisite for efficient searching and many other operations.

Key Takeaway: Different search algorithms have different requirements and performance characteristics. Linear search works on any data but is slow. Binary search is fast but requires sorted data. Choose the right algorithm based on your data characteristics and performance needs.