Linear Search and Binary Search

Linear search examines elements in order and works without sorted input. Binary search repeatedly halves an ordered candidate range, requiring sorted data or another monotone predicate. We provide separate linear, iterative binary and recursive binary functions. All return the first matching zero-based index, including when duplicates exist; the binary functions first locate the earliest value at least the target and then check equality.

Prerequisites: Sorting; loops; recursion; indexed vectors.

Build the idea

1. 1. Start with a complete scan

   linear checks a[0],a[1],… and returns immediately on equality. If the loop finishes, the target is absent. This needs no sorted assumption and returns the first occurrence naturally. In the combined program the input is sorted because the same array must also satisfy the binary-search functions’ precondition.

2. 2. Search a boundary rather than a guessed match

   Maintain lo=0 and hi=n. The first position whose value is ≥target lies between them, allowing n as an absent-after-all-elements sentinel. At mid, if a[mid]<target, sorted order proves every position through mid is too small, so lo=mid+1. Otherwise the boundary is at or before mid, so hi=mid. Neither update discards a possible first occurrence.

3. 3. Prove progress and handle empty ranges

   With lo<hi, mid is a valid element index below n. Each update strictly shortens the interval. At lo==hi no inspection is needed; the result may equal n. Check result<n before a[result]. For an empty vector the loop executes zero times and returns zero, which becomes −1 after the equality guard. The recursive version uses exactly the same interval updates and base case.

4. 4. Trace duplicate values

   For [1,3,3,5,8] and target 3, start [0,5). Mid 2 contains 3, so hi=2; mid 1 contains 3, so hi=1; mid 0 contains 1, so lo=1. Boundary 1 is the first match. Returning immediately at the first equal mid would instead produce index 2, violating the first-occurrence contract.

5. 5. Account for preprocessing

   One binary query on an already sorted vector takes O(log n). Sorting an unsorted vector first costs O(n log n) and changes indices. For one lookup, linear search may be simpler and faster overall. For many lookups on static data, sorting once can pay off. Recursive binary search uses stack frames even though the iterative version does not.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
int linear(const std::vector<int>&a,int target){
    for(int i=0;i<(int)a.size();++i){
        if(a[i]==target){
            return i;
        }
    }
    return -1;
}
int lowerIterative(const std::vector<int>&a,int target){
    int lo=0,hi=(int)a.size(); // First >= target is in [lo,hi], hi may be n.
    while(lo<hi){
        int mid=lo+(hi-lo)/2;
        if(a[mid]<target){
            lo=mid+1;
        }
        else{
            hi=mid;
        }
    }
    return lo;
}
int lowerRecursive(const std::vector<int>&a,int target,int lo,int hi){
    if(lo==hi){
        return lo;
    }
    int mid=lo+(hi-lo)/2;
    if(a[mid]<target){
        return lowerRecursive(a,target,mid+1,hi);
    }
    return lowerRecursive(a,target,lo,mid);
}
int main(){
    int n,target;
    std::cin>>n>>target;
    std::vector<int>a(n);
    for(int&x:a){
        std::cin>>x;
    }
    int i=lowerIterative(a,target),r=lowerRecursive(a,target,0,n);
    int iterative=(i<n&&a[i]==target)?i:-1;
    int recursive=(r<n&&a[r]==target)?r:-1;
    std::cout<<linear(a,target)<<' '<<iterative<<' '<<recursive<<'\n';
}

Complexity analysis

Linear search O(n) time and O(1) auxiliary memory. Iterative binary search O(log(n+1)) time/O(1) space; recursive binary search O(log(n+1)) time and stack. The combined program also runs linear search, so TOTAL time is O(n), with O(n) input storage and logarithmic auxiliary stack. Sorting is not performed and is not included.

Example input and output

Read n target (0≤n≤200000), then n integers sorted NONDECREASINGLY. Print the first target index from linear, iterative binary and recursive binary search, or −1 from each if absent.

Input

5 3
1 3 3 5 8

Output

1 1 1

Both boundary searches move left on equality and locate the first 3 at index 1.

Practical applications

Use linear search for unsorted data or a single small scan, binary search for repeated sorted-vector lookups, and lower_bound/upper_bound for standard boundary operations. Linked containers do not provide constant-time midpoint access, so this array analysis does not directly apply to all iterators.

Check your understanding

Why is an equality check needed after lower-bound search?

Put it into practice

Test empty input, all-equal data, absent targets and endpoints.