Module 4: Searching Algorithms

Searching is not just about finding an element.
In interviews and competitive programming, searching is about reducing the search space intelligently.

Most high-level problems are disguised as:

• “Find the minimum…”
• “Find the first occurrence…”
• “Find the maximum possible value…”
  All of these are search problems in disguise.

Linear Search

Concept

Linear search checks elements sequentially, one by one.

It does not require sorting, which makes it universally applicable but inefficient for large inputs.

How It Works

• Start from index 0
• Compare each element with target
• Stop when found or array ends

Example

int search(int[] arr, int key){
    for(int i = 0; i < arr.length; i++){
        if(arr[i] == key)
            return i;
    }
    return -1;
}

Analysis

• Best case: Element at index 0 → O(1)
• Worst case: Element not present → O(n)
• Space complexity: O(1)

When Linear Search is Preferred

• Small datasets
• Unsorted data
• One-time search
• Linked lists

Interview insight:
If constraints are small (n ≤ 10³), linear search is acceptable.

Binary Search

Core Idea

Binary search works on the principle:

“If the data is sorted, we don’t need to look everywhere.”

Each step removes half of the remaining elements.

Preconditions

• Data must be sorted
• Random access must be possible (arrays)

Binary Search (Iterative)

Why Iterative is Preferred

• No recursion stack
• Faster
• Less memory usage

Code

int binarySearch(int[] arr, int key){
    int low = 0, high = arr.length - 1;

    while(low <= high){
        int mid = low + (high - low) / 2;

        if(arr[mid] == key)
            return mid;
        else if(arr[mid] < key)
            low = mid + 1;
        else
            high = mid - 1;
    }
    return -1;
}

Why low + (high - low) / 2?

Prevents integer overflow when low and high are large.

Binary Search (Recursive)

When Recursive Version is Used

• Teaching recursion
• Conceptual clarity
• Divide & conquer understanding

Code

int binarySearch(int[] arr, int low, int high, int key){
    if(low > high) return -1;

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

    if(arr[mid] == key) return mid;
    else if(arr[mid] < key)
        return binarySearch(arr, mid + 1, high, key);
    else
        return binarySearch(arr, low, mid - 1, key);
}

Comparison

• Time: O(log n)
• Space: O(log n) (stack)

Interview tip:
Use iterative unless recursion is explicitly asked.

Binary Search on Answers (Most Important Topic)

What Does It Mean?

Instead of searching in an array, we search within a range of possible answers.

Used when:

• Answer lies between a minimum and maximum value
• Problem has a monotonic nature

Key Pattern

• Guess an answer
• Check if it is valid
• Move left or right

Example Problems

• Minimum speed
• Maximum capacity
• Allocate books
• Ship packages
• Aggressive cows

Generic Template

while(low <= high){
    int mid = low + (high - low) / 2;

    if(isPossible(mid)){
        answer = mid;
        high = mid - 1;
    } else {
        low = mid + 1;
    }
}

Interview Insight

If problem says:

• “minimum possible”
• “maximum possible”
• “optimize”
  Think Binary Search on Answer.

Lower Bound & Upper Bound

Lower Bound

First index where element ≥ target.

Example:

int lowerBound(int[] arr, int key){
    int low = 0, high = arr.length;
    while(low < high){
        int mid = (low + high) / 2;
        if(arr[mid] < key)
            low = mid + 1;
        else
            high = mid;
    }
    return low;
}

Upper Bound

First index where element > target.

Used together to find frequency:

frequency = upperBound - lowerBound;

Used heavily in:

• Competitive programming
• STL-based solutions
• Range problems

Search in Rotated Sorted Array

Problem Insight

Even after rotation:

• One half is always sorted

Example

[4,5,6,7,0,1,2]

Decision Logic

1. Check which half is sorted
2. Check if target lies in that half
3. Discard the other half

Complexity

• Time: O(log n)
• Space: O(1)

This problem tests logical decision-making, not memorization.

Infinite Array Search

Problem Scenario

• Array size is unknown
• You cannot use length

Strategy

• Start with small range
• Expand exponentially

int low = 0, high = 1;
while(arr[high] < key){
    low = high;
    high = high * 2;
}

Then apply binary search.

This is common in:

• System design interviews
• Streamed data problems

Peak Element Problems

Definition

An element greater than its neighbors.

Key fact:

Every array has at least one peak.

Why Binary Search Works

If slope is rising → peak on right
If slope is falling → peak on left

Binary Search Logic

if(arr[mid] < arr[mid + 1])
    low = mid + 1;
else
    high = mid;

Time: O(log n)

Ternary Search

When to Use

Used on unimodal functions (first increases, then decreases).

Divides range into three parts.

Used in:

• Mathematical optimization
• Competitive programming geometry problems

Less common in interviews, but important conceptually.

Applications of Binary Search

Binary search appears in:

• Databases (indexing)
• Operating systems
• Scheduling algorithms
• Load balancing
• Machine learning thresholds
• Competitive programming