Searching

Searching is one of the most common things computers do. Every database query, every “find” in your text editor, every Google search - all searching.

This guide covers every searching algorithm you need to know, from the simplest to the most clever.

What is Searching?

Searching means: given a list of things, find a specific one.

More precisely - given a collection and a target value, tell me:

• Does the target exist in the collection?
• If yes, where is it (what index)?

What Interviewers Actually Judge You On

Every searching problem in an interview is judged on these dimensions:

1. What data structure are we searching? (array, matrix, tree)
2. Is the data sorted or unsorted?
3. Time complexity - how fast?
4. Space complexity - how much memory?
5. Edge cases - empty array, target not found, duplicates
6. Why this algorithm and not a different one?

Always answer these before writing code.

Linear Search

The Idea

Go through the list one element at a time. Check each one. Stop when you find the target or run out of elements.

It is the simplest search. No tricks, no requirements on the data.

Array: [40, 10, 30, 20]
Target: 30

Check index 0 -> 40 ≠ 30
Check index 1 -> 10 ≠ 30
Check index 2 -> 30 = 30 ✓ Found at index 2

Code

def linear_search(arr: list[int], target: int) -> int:
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1   # not found

Time Complexity

Case	When	Time
Best	Target is the very first element	O(1)
Average	Target is somewhere in the middle	O(n)
Worst	Target is last or not there at all	O(n)

Space: O(1) - no extra memory used.

When to Use Linear Search

• The array is unsorted (you have no choice)
• The array is very small
• You are searching in a linked list (can’t jump to middle)
• You only need to search once (not worth sorting first)
• Working with streaming data that arrives one piece at a time

Note

Linear search is the baseline. If you use it when a faster option exists, interviewers expect you to justify why.

Binary Search

The One Rule

Binary Search only works on sorted data.

This is the most important thing about binary search. If the array is not sorted, binary search gives wrong answers. No exceptions.

The Idea

Instead of checking every element from left to right, make a smarter guess:

• Look at the middle element
• If it is the target - done
• If target is smaller - search only the left half
• If target is larger - search only the right half
• Repeat on the remaining half

Each step cuts the search space in half. This is why it is so fast.

Sorted array:
index:  0   1   2   3   4   5   6
value: [2,  4,  6,  8,  10, 12, 14]
target = 10

Step 1: mid = 3, value = 8
        8 < 10, so search right half

Step 2: mid = 5, value = 12
        12 > 10, so search left

Step 3: mid = 4, value = 10
        Found at index 4

Iterative Code

def binary_search(arr: list[int], target: int) -> int:
    start = 0
    end = len(arr) - 1

    while start <= end:
        mid = start + (end - start) // 2   # safe mid calculation

        if arr[mid] == target:
            return mid
        elif arr[mid] > target:
            end = mid - 1    # search left half
        else:
            start = mid + 1  # search right half

    return -1  # not found

Tip

Why write mid = start + (end - start) // 2 instead of (start + end) // 2?

In languages like Java or C++, start + end can overflow the integer limit if both are very large numbers. The safer formula avoids this. Interviewers expect you to know this.

Time Complexity

Case	Time
Best	O(1) - target is at the middle
Average	O(log n)
Worst	O(log n)

Space: O(1) - no extra memory.

Why O(log n)? Because every step cuts the remaining elements in half. Starting with n elements: after 1 step you have n/2, after 2 steps n/4, and so on. You reach 1 element after log₂ n steps.

Recursive Code

The same idea, written using a function that calls itself:

def binary_search_recursive(arr, target, start, end):
    if start > end:
        return -1   # base case - not found

    mid = start + (end - start) // 2

    if arr[mid] == target:
        return mid
    elif arr[mid] > target:
        return binary_search_recursive(arr, target, start, mid - 1)
    else:
        return binary_search_recursive(arr, target, mid + 1, end)

How to call it:

result = binary_search_recursive(arr, target, 0, len(arr) - 1)

Space for recursive version: O(log n) - because each call stays on the call stack until it returns.

Iterative vs Recursive

	Iterative	Recursive
Space	O(1)	O(log n)
Readability	Slightly more code	Cleaner to read
Preferred when	Memory is important	Clarity matters

In interviews, iterative is preferred unless the question specifically asks for recursive.

Binary Search on a 2D Matrix (Flattened)

When This Works

This technique works when the matrix has these two properties:

1. Each row is sorted left to right
2. The first element of the next row is greater than the last element of the previous row

[0,  2,  3,  5,  8 ]
[10, 12, 15, 18, 21]
[23, 26, 29, 33, 40]

If you read this row by row, it is just one long sorted list:

[0, 2, 3, 5, 8, 10, 12, 15, 18, 21, 23, 26, 29, 33, 40]

The Key Formula - Converting 1D index to 2D position

When you calculate a mid index in the flattened array, you need to convert it back to a row and column:

row = mid // total_columns
col = mid % total_columns

Example: mid = 7, total columns = 5

row = 7 // 5 = 1
col = 7 % 5  = 2
-> element is at arr[1][2]

Code

def binary_search_2d(arr, target):
    rows = len(arr)
    cols = len(arr[0])

    start = 0
    end = rows * cols - 1  # treat as flat 1D array

    while start <= end:
        mid = start + (end - start) // 2
        r = mid // cols
        c = mid % cols

        if arr[r][c] == target:
            return (r, c)
        elif arr[r][c] > target:
            end = mid - 1
        else:
            start = mid + 1

    return (-1, -1)

Time: O(log(m * n)) where m = rows, n = columns. Space: O(1)

Caution

This only works when the matrix is globally sorted (each row continues from the previous). If rows are sorted independently, use the staircase search below.

Staircase Search - Row and Column Sorted Matrix

The Problem

What if the matrix looks like this?

 1   4   7  11
 2   5   8  12
 3   6   9  16
10  13  14  17

Each row is sorted left to right. Each column is sorted top to bottom. But the matrix is NOT globally sorted - you cannot flatten it.

Normal binary search does not work here.

The Smart Strategy - Start at Top-Right

Start at the top-right corner of the matrix and use this logic:

• If current value equals target -> found
• If current value is greater than target -> move left (smaller values are to the left)
• If current value is less than target -> move down (larger values are below)

Why top-right? Because from that position, left always means smaller and down always means larger. Every step eliminates an entire row or column.

Walkthrough - Searching for 6

Start at top-right: 11

11 > 6 -> move left  -> 7
7  > 6 -> move left  -> 4
4  < 6 -> move down  -> 5
5  < 6 -> move down  -> 6

Found!

Code

def search_matrix(matrix, target):
    rows = len(matrix)
    cols = len(matrix[0])

    r = 0
    c = cols - 1  # start at top-right

    while r < rows and c >= 0:
        if matrix[r][c] == target:
            return (r, c)
        elif matrix[r][c] > target:
            c -= 1   # move left
        else:
            r += 1   # move down

    return (-1, -1)

Time: O(m + n) - at most m + n steps total, since each step eliminates a row or column. Space: O(1)

Ternary Search

The Idea

Instead of splitting into 2 halves, split into 3 equal parts. Check two midpoints instead of one.

mid1 = start + (end - start) // 3
mid2 = end - (end - start) // 3

You then check arr[mid1] and arr[mid2] to decide which third to search.

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

The Truth About Ternary Search

Ternary search sounds faster (log base 3 instead of 2), but it actually does more comparisons than binary search at each step. Binary search is almost always the better choice.

Ternary search is mainly used for:

• Finding the maximum/minimum of a unimodal function (one peak, no flat regions)
• Certain competitive programming problems

Note

If an interviewer asks why you would not use ternary search for a sorted array - the answer is that binary search does fewer total comparisons and is simpler to implement.

Comparison Table

Algorithm	Requirement	Time	Space	Use When
Linear Search	Any data	O(n)	O(1)	Unsorted, small, or streaming data
Binary Search (iterative)	Sorted array	O(log n)	O(1)	Sorted array, production code
Binary Search (recursive)	Sorted array	O(log n)	O(log n)	Sorted array, clarity matters
2D Binary Search	Globally sorted matrix	O(log(m*n))	O(1)	Matrix where rows connect
Staircase Search	Row + column sorted	O(m + n)	O(1)	Matrix sorted independently per row/col
Ternary Search	Sorted / unimodal	O(log n)	O(1)	Unimodal functions only

Interview Checklist

Before writing any search code in an interview:

1. Ask about the data - is it sorted? unsorted? a matrix?

2. Choose the right algorithm - sorted -> binary, unsorted -> linear, matrix -> depends on which type

3. Handle edge cases - what if the array is empty? what if the target appears multiple times?

4. Write mid = start + (end - start) // 2 - never (start + end) // 2

5. Explain your loop invariant - for binary search: “at every step, if the target exists, it must be between start and end”

6. State time and space complexity

Quick Reference

Linear Search

O(n) time, O(1) space. Works on anything. No sorting needed. Use for unsorted or small data.

Binary Search

O(log n) time, O(1) space. Requires sorted data. Cuts search space in half each step.

Safe Mid Formula

Always use mid = start + (end - start) // 2 to avoid integer overflow.

2D Flattened

Treat globally sorted matrix as 1D. Convert index with row = mid // cols, col = mid % cols.

Staircase Search

Start top-right. Go left if too big, go down if too small. Each step removes a row or column.

Ternary Search

Divides into 3 parts. Useful only for unimodal functions, not regular sorted arrays.

Summary

When to Use What

• Unsorted data -> Linear Search
• Sorted 1D array -> Binary Search (iterative)
• Globally sorted matrix -> 2D Binary Search
• Row and column sorted matrix -> Staircase Search
• Finding peak of a curve -> Ternary Search

Key Rules

• Binary search REQUIRES sorted data - this is non-negotiable
• Always use safe mid formula: start + (end - start) // 2
• Iterative binary search uses O(1) space; recursive uses O(log n)
• Staircase search is O(m+n), not O(log mn) - different tradeoff

Interview Tips

• State your assumption about sorted vs unsorted first
• Explain the loop invariant for binary search
• For 2D matrices, ask which type it is before picking an approach
• Linear search is a valid answer - just explain why it is appropriate

Tip

Binary search is one of the most tested topics in interviews. Practice writing it from memory, without bugs, in under 2 minutes. The start <= end condition and the safe mid formula are the two places people slip up most.