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

1. Implement each algorithm - Don't just read; code them yourself
2. Visualize the process - Draw how each search progresses
3. Compare performance - Time algorithms with different input sizes
4. Understand prerequisites - Some algorithms require sorted data
5. 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<int>& arr, int target) {
    for (size_t i = 0; i < arr.size(); i++) {
        if (arr[i] == target) {
            return i;
        }
    }
    return -1;
}

int main() {
    vector<int> 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<int>& 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<int> 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<int>& 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<int> 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<int>& 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<int> 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

Common Mistakes

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

Debugging Tips

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

Mini Exercises

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

Review Questions

1. Why can't binary search be used on unsorted arrays?
2. What's the space complexity difference between iterative and recursive binary search?
3. When is interpolation search better than binary search?
4. Why is jump search useful for linked lists compared to binary search?
5. 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.