Go's simplicity makes binary search easy to read on a whiteboard — slices, integer indices, and no hidden overflow surprises with size_t. Many backend interviews use Go; this pattern shows up constantly.

For algorithm theory and interview variants, read [Binary Search Algorithm: A Coding Interview Guide](/articles/binary-search) first.

## Prerequisites

- Slice sorted in ascending order
- **O(log n)** time, **O(1)** extra space (iterative)

## Iterative binary search

```go
func binarySearch(arr []int, x int) int {
    lo, hi := 0, len(arr)-1

    for lo <= hi {
        mid := lo + (hi-lo)/2

        if arr[mid] == x {
            return mid
        }
        if arr[mid] > x {
            hi = mid - 1
        } else {
            lo = mid + 1
        }
    }

    return -1
}
```

Go integers are signed and arbitrary precision is not an issue for indices — `(lo + hi) / 2` is usually safe, but `lo + (hi-lo)/2` is still the interview-standard form.

## Recursive version

```go
func binarySearchRec(arr []int, x, lo, hi int) int {
    if lo > hi {
        return -1
    }
    mid := lo + (hi-lo)/2

    if arr[mid] == x {
        return mid
    }
    if arr[mid] > x {
        return binarySearchRec(arr, x, lo, mid-1)
    }
    return binarySearchRec(arr, x, mid+1, hi)
}

// Call: binarySearchRec(arr, x, 0, len(arr)-1)
```

## sort.Search (idiomatic Go)

The standard library uses binary search internally:

```go
import "sort"

arr := []int{1, 3, 5, 7, 9}
x := 5

// Smallest index i where arr[i] >= x
idx := sort.Search(len(arr), func(i int) bool {
    return arr[i] >= x
})

found := idx < len(arr) && arr[idx] == x
_ = found
```

`sort.Search` is the Go equivalent of lower bound. It returns `len(arr)` if no element satisfies the predicate.

## Lower bound helper

```go
func lowerBound(arr []int, x int) int {
    lo, hi := 0, len(arr)
    for lo < hi {
        mid := lo + (hi-lo)/2
        if arr[mid] < x {
            lo = mid + 1
        } else {
            hi = mid
        }
    }
    return lo
}
```

Use when the problem asks for insertion point or first index where `arr[i] >= x`.

## Go-specific tips

- Check empty slice: `if len(arr) == 0 { return -1 }`
- Slices are references — no copying when passing to functions
- Naming: `lo`/`hi` or `left`/`right` — stay consistent
- Run tests with `go test` and table-driven cases in real projects

## Example test

```go
func TestBinarySearch(t *testing.T) {
    arr := []int{1, 3, 5, 7, 9}
    if got := binarySearch(arr, 5); got != 2 {
        t.Fatalf("got %d, want 2", got)
    }
    if got := binarySearch(arr, 4); got != -1 {
        t.Fatalf("got %d, want -1", got)
    }
}
```

## Complexity

- **Time:** O(log n)
- **Space:** O(1) iterative, O(log n) recursive

## Related reading

- [Binary Search Algorithm: A Coding Interview Guide](/articles/binary-search) — full walkthrough and common mistakes
- [How to analyze time complexity](/articles/time-complexity) — why binary search is O(log n)

How to Implement Binary Search in Go

C binary search appears in systems interviews, embedded roles, and any loop where you need explicit control over memory and indices. The logic is the same as other languages — only syntax and pointer habits differ.

For the conceptual guide (two methods, jump search, interview variants), see [Binary Search Algorithm: A Coding Interview Guide](/articles/binary-search).

## Prerequisites

- Sorted array of integers (ascending)
- Array length `n` passed explicitly or known from context
- **O(log n)** time, **O(1)** space for iterative code

## Iterative binary search

```c
int binary_search(const int *arr, int n, int x) {
    int lo = 0;
    int hi = n - 1;

    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;

        if (arr[mid] == x) return mid;
        if (arr[mid] > x) hi = mid - 1;
        else lo = mid + 1;
    }

    return -1;
}
```

Use `const int *arr` when the function does not modify the array. Always compute `mid` as `lo + (hi - lo) / 2` to avoid integer overflow.

## Recursive version

```c
int binary_search_rec(const int *arr, int x, int lo, int hi) {
    if (lo > hi) return -1;

    int mid = lo + (hi - lo) / 2;

    if (arr[mid] == x) return mid;
    if (arr[mid] > x) return binary_search_rec(arr, x, lo, mid - 1);
    return binary_search_rec(arr, x, mid + 1, hi);
}

// Call: binary_search_rec(arr, x, 0, n - 1);
```

## Complete example with main

```c
#include <stdio.h>

int binary_search(const int *arr, int n, int x) {
    int lo = 0, hi = n - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] == x) return mid;
        if (arr[mid] > x) hi = mid - 1;
        else lo = mid + 1;
    }
    return -1;
}

int main(void) {
    int arr[] = {1, 3, 5, 7, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("%d\n", binary_search(arr, n, 5)); // 2
    return 0;
}
```

## C-specific pitfalls

- **No built-in length** — pass `n` or track size with `sizeof` for static arrays only
- **Unsigned pitfalls** — keep `lo` and `hi` as `int`; mixing unsigned types breaks `hi = mid - 1` when `mid` is 0
- **Do not pointer-arithmetic past bounds** — indices only
- Empty array: if `n == 0`, return `-1` before the loop

## bsearch from stdlib

C provides `bsearch` in `<stdlib.h>`. It requires a comparator function and is less common in interviews:

```c
#include <stdlib.h>

int compare(const void *a, const void *b) {
    return *(const int *)a - *(const int *)b;
}

// int *found = bsearch(&key, arr, n, sizeof(int), compare);
```

Prefer writing the loop by hand in interviews.

## Complexity

- **Time:** O(log n)
- **Space:** O(1) iterative

## Related reading

- [Binary Search Algorithm: A Coding Interview Guide](/articles/binary-search) — algorithm theory and interview follow-ups
- [Binary search in C++](/articles/binary-search-cpp) — STL `lower_bound` and `upper_bound` alternatives

How to Implement Binary Search in C

C++ interviews often expect comfort with both raw loops and the STL algorithms `<algorithm>`. Binary search on sorted data is O(log n) either way — know both styles.

Start with the full concept guide: [Binary Search Algorithm: A Coding Interview Guide](/articles/binary-search).

## Prerequisites

- Sorted container (`vector`, array, or any random-access sequence)
- **O(log n)** search time

## Template implementation

```cpp
#include <vector>

int binarySearch(const std::vector<int>& arr, int x) {
    int lo = 0;
    int hi = static_cast<int>(arr.size()) - 1;

    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;

        if (arr[mid] == x) return mid;
        if (arr[mid] > x) hi = mid - 1;
        else lo = mid + 1;
    }

    return -1;
}
```

Cast `arr.size()` to `int` when mixing with signed indices, or use `size_t` consistently with care at boundaries.

## Generic template (interview bonus)

```cpp
template<typename T>
int binarySearch(const std::vector<T>& arr, const T& x) {
    int lo = 0, hi = static_cast<int>(arr.size()) - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] == x) return mid;
        if (arr[mid] > x) hi = mid - 1;
        else lo = mid + 1;
    }
    return -1;
}
```

## STL: lower_bound and upper_bound

The C++ standard library implements binary search in O(log n):

```cpp
#include <algorithm>
#include <vector>

std::vector<int> arr = {1, 3, 5, 5, 7, 9};
int x = 5;

// First element >= x
auto it = std::lower_bound(arr.begin(), arr.end(), x);
bool found = it != arr.end() && *it == x;
int idx = static_cast<int>(it - arr.begin());

// First element > x
auto it2 = std::upper_bound(arr.begin(), arr.end(), x);

// std::binary_search returns bool only
bool exists = std::binary_search(arr.begin(), arr.end(), x);
```

`lower_bound` / `upper_bound` are essential for "first/last occurrence" and range-count problems.

## Recursive version

```cpp
int binarySearchRec(const std::vector<int>& arr, int x, int lo, int hi) {
    if (lo > hi) return -1;
    int mid = lo + (hi - lo) / 2;
    if (arr[mid] == x) return mid;
    if (arr[mid] > x) return binarySearchRec(arr, x, lo, mid - 1);
    return binarySearchRec(arr, x, mid + 1, hi);
}
```

## C++ interview tips

- Prefer `vector` over raw arrays — size is tracked
- Avoid `arr[mid]` with unsigned `mid` when `hi` can underflow — stick to signed `int` indices in the classic template
- State complexity: **O(log n)** time, **O(1)** space (iterative)
- When allowed, STL calls show library fluency; when asked to implement, use the while loop

## Complexity

- **Time:** O(log n)
- **Space:** O(1) iterative, O(log n) recursive

## Related reading

- [Binary Search Algorithm: A Coding Interview Guide](/articles/binary-search) — core algorithm and variants
- [Binary search in C](/articles/binary-search-c) — pointer-based version without STL
- [How to analyze time complexity](/articles/time-complexity) — Big O fundamentals

How to Implement Binary Search in C++

Java remains a top language for FAANG-style interviews. Binary search on sorted arrays is a must-know pattern — and Java's integer overflow rules make midpoint calculation especially worth getting right.

Read the language-agnostic explanation first: [Binary Search Algorithm: A Coding Interview Guide](/articles/binary-search).

## Prerequisites

- Input array sorted ascending
- **O(log n)** time per search, **O(1)** space (iterative)

## Iterative implementation

```java
public static int binarySearch(int[] arr, int x) {
    int lo = 0;
    int hi = arr.length - 1;

    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;

        if (arr[mid] == x) return mid;
        if (arr[mid] > x) hi = mid - 1;
        else lo = mid + 1;
    }

    return -1;
}
```

**Critical in Java:** never write `int mid = (lo + hi) / 2` on large arrays — `lo + hi` can overflow. Always use `lo + (hi - lo) / 2`.

## Recursive implementation

```java
public static int binarySearchRecursive(int[] arr, int x, int lo, int hi) {
    if (lo > hi) return -1;

    int mid = lo + (hi - lo) / 2;

    if (arr[mid] == x) return mid;
    if (arr[mid] > x) return binarySearchRecursive(arr, x, lo, mid - 1);
    return binarySearchRecursive(arr, x, mid + 1, hi);
}

// Call: binarySearchRecursive(arr, x, 0, arr.length - 1);
```

Recursive depth is O(log n) — safe for arrays up to millions of elements.

## Arrays.binarySearch

Java provides a built-in binary search:

```java
import java.util.Arrays;

int[] arr = {1, 3, 5, 7, 9};
int idx = Arrays.binarySearch(arr, 5); // returns 2 if found

// If not found, returns -(insertionPoint) - 1
int missing = Arrays.binarySearch(arr, 4); // negative index
```

Decode negative results: `insertionPoint = -(result + 1)`. In interviews, implement manually unless told otherwise.

## Lower bound (first index >= x)

```java
public static int lowerBound(int[] arr, int x) {
    int lo = 0, hi = arr.length;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] < x) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}
```

Use this for "first occurrence" and sorted insertion point problems.

## Java interview tips

- Use `int[]` unless the problem requires objects — autoboxing adds noise
- Guard empty input: `if (arr.length == 0) return -1;`
- For `List<Integer>`, convert to array or use indexed `get(mid)` — avoid `subList` copies
- Mention **O(log n)** time and **O(1)** auxiliary space when done

## Complexity

- **Time:** O(log n)
- **Space:** O(1) iterative, O(log n) recursive stack

## Related reading

- [Binary Search Algorithm: A Coding Interview Guide](/articles/binary-search) — full algorithm explanation and variants
- [How to analyze time complexity](/articles/time-complexity) — Big O and loop analysis

How to Implement Binary Search in Java

Python is one of the most common languages in coding interviews. If the input is sorted, binary search should be your reflex — and Python gives you both hand-rolled loops and a built-in `bisect` module.

For the full algorithm walkthrough (two methods, complexity, and interview variants), start with our [Binary Search Algorithm guide](/articles/binary-search).

## Prerequisites

- The array must be sorted in ascending order
- Time complexity: **O(log n)** per query
- Space: **O(1)** iterative, **O(log n)** recursive (call stack)

## Iterative binary search

The standard interview template uses `lo` and `hi` pointers:

```python
def binary_search(arr: list[int], x: int) -> int:
    lo, hi = 0, len(arr) - 1

    while lo <= hi:
        mid = lo + (hi - lo) // 2

        if arr[mid] == x:
            return mid
        if arr[mid] > x:
            hi = mid - 1
        else:
            lo = mid + 1

    return -1
```

Use `lo + (hi - lo) // 2` instead of `(lo + hi) // 2` — interviewers appreciate overflow-safe midpoint math even though Python integers do not overflow.

## Recursive version

```python
def binary_search_recursive(arr: list[int], x: int, lo: int = 0, hi: int | None = None) -> int:
    if hi is None:
        hi = len(arr) - 1

    if lo > hi:
        return -1

    mid = lo + (hi - lo) // 2

    if arr[mid] == x:
        return mid
    if arr[mid] > x:
        return binary_search_recursive(arr, x, lo, mid - 1)
    return binary_search_recursive(arr, x, mid + 1, hi)
```

Prefer iterative in timed interviews — fewer stack concerns and easier to debug on a whiteboard.

## Using bisect (production Python)

The standard library module `bisect` implements binary search on sorted lists:

```python
import bisect

arr = [1, 3, 5, 7, 9]
x = 5

# Index where x would be inserted (leftmost)
idx = bisect.bisect_left(arr, x)
found = idx < len(arr) and arr[idx] == x

# bisect_right — insert after existing equal elements
idx_right = bisect.bisect_right(arr, x)
```

In interviews, write the loop yourself unless the interviewer explicitly allows library calls. In production code, prefer `bisect`.

## Lower bound pattern

Find the first index where `arr[i] >= x`:

```python
def lower_bound(arr: list[int], x: int) -> int:
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] < x:
            lo = mid + 1
        else:
            hi = mid
    return lo
```

This template solves "first occurrence" and "insert position" problems. See the [main binary search guide](/articles/binary-search) for when to use `lo <= hi` vs `lo < hi`.

## Python-specific tips for interviews

- Type hints (`list[int]`) are optional but show clarity
- `//` is integer division — always use it for midpoints
- List slicing (`arr[lo:hi]`) creates copies — **never slice** in binary search; move indices instead
- Test empty list: `binary_search([], 1)` should return `-1`

## Complexity

- **Time:** O(log n) comparisons
- **Space:** O(1) iterative, O(log n) recursive

## Related reading

- [Binary Search Algorithm: A Coding Interview Guide](/articles/binary-search) — concepts, variants, and common mistakes
- [How to analyze time complexity](/articles/time-complexity) — why halving the range is O(log n)

How to Implement Binary Search in Python

Binary search is one of the highest-leverage patterns in coding interviews. Once you recognize "sorted input" or "find boundary in monotonic space," you can often drop from O(n) to O(log n) — and interviewers will expect you to.

This guide covers the core idea, two standard implementations, and the follow-ups that separate a passing answer from a strong one.

## When linear search is enough

The straightforward way to find a value in an array is a single loop:

```javascript
function linearSearch(arr, x) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === x) return i;
  }
  return -1;
}
```

Time complexity: **O(n)** — in the worst case you inspect every element. If the array is unsorted and you have no extra structure, that is optimal. There is no shortcut without additional information.

## Why sorting unlocks O(log n)

When the array is **sorted ascending**, order tells you where to look next. Compare against the middle element:

- Equal → found
- Target is smaller → search the left half only
- Target is larger → search the right half only

Each comparison eliminates half the remaining elements. That halving is what gives **O(log n)** time.

Interview tip: say this out loud before coding — "I'll maintain a search range and cut it in half each step."

## Method 1: Classic range search

Think of looking up a word in a dictionary. You keep an active range `[lo, hi]` that starts as the full array. Repeatedly inspect the midpoint and narrow to the left or right half.

```javascript
function binarySearch(arr, x) {
  let lo = 0;
  let hi = arr.length - 1;

  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);

    if (arr[mid] === x) return mid;
    if (arr[mid] > x) hi = mid - 1;
    else lo = mid + 1;
  }

  return -1;
}
```

The active region shrinks by at least half each iteration, so the loop runs at most **⌈log₂(n + 1)⌉** times → **O(log n)**.

### Avoid integer overflow

In languages like Java or C++, `lo + hi` can overflow. Use `lo + (hi - lo) / 2` (shown above). In JavaScript numbers are doubles so overflow is rare, but interviewers still like hearing you know the idiom.

### Loop invariant to remember

When the loop ends with `lo > hi`, the target is not present. Some variants use `lo < hi` for "first position where…" problems — know which template you are using and stick to it.

## Method 2: Jump search with shrinking step size

A second pattern scans left to right but jumps in large steps, then halves the jump size as you hone in — like galloping across the array and slowing down near the target.

Start with jump length `b = ⌊n/2⌋`. For each jump size (n/2, n/4, n/8, … down to 1), advance the pointer while the landing spot is still safe and not past the target. After all jumps, check the final index.

```javascript
function binarySearchJump(arr, x) {
  const n = arr.length;
  let k = 0;

  for (let b = Math.floor(n / 2); b >= 1; b = Math.floor(b / 2)) {
    while (k + b < n && arr[k + b] <= x) {
      k += b;
    }
  }

  if (arr[k] === x) return k;
  return -1;
}
```

The inner `while` moves `k` forward at most once per jump level, and there are O(log n) levels — still **O(log n)** overall.

This variant is less common in live coding but useful for **lower bound** style problems (first index where value ≥ x). Many standard libraries expose this as `bisect_left` / `lower_bound`.

## Beyond "find exact value"

Interviewers rarely ask for vanilla search on a plain array. They ask variants:

- **First / last occurrence** of x in a sorted array with duplicates
- **Search in rotated sorted array**
- **Find peak / minimum in rotated array**
- **Binary search on answer** — monotonic predicate over the answer space (e.g. "minimum capacity to ship packages in D days")

The template changes slightly, but the engine is the same: maintain a range, discard half based on a comparison.

## Complexity summary

- **Linear scan** — unsorted OK, O(n) time, O(1) space
- **Binary search (Method 1)** — sorted required, O(log n) time, O(1) space
- **Jump binary (Method 2)** — sorted required, O(log n) time, O(1) space

Recursive binary search uses O(log n) call stack space — mention that if you implement it recursively instead of iteratively.

## Common mistakes in interviews

- Forgetting to handle **empty array** or single-element edge cases
- Off-by-one errors on `hi = mid - 1` vs `hi = mid` in lower-bound templates
- Using binary search on unsorted data without sorting first (adds O(n log n) preprocessing)
- Infinite loops when `lo` and `hi` do not converge — test with 2-element arrays

## How to practice

1. Implement Method 1 from memory on a whiteboard.
2. Solve "find first and last position of element" on LeetCode-style platforms.
3. Apply the [coding interview framework](/coding) — clarify sorted order, walk an example, then code.
4. State **O(log n)** time and **O(1)** extra space before you run test cases.

## Related reading

### Implementations by language

- [Binary search in Python](/articles/binary-search-python)
- [Binary search in Java](/articles/binary-search-java)
- [Binary search in C](/articles/binary-search-c)
- [Binary search in C++](/articles/binary-search-cpp)
- [Binary search in Go](/articles/binary-search-go)

### More algorithm guides

- [How to analyze time complexity](/articles/time-complexity) — why halving the search space is O(log n)
- [Sorting algorithms: time complexity cheat sheet](/articles/sorting-algorithms-time-complexity) — when you sort first, then binary search

Binary Search Algorithm: A Coding Interview Guide

Nearly every coding interview ends with: "What's the time complexity?" You are not being asked to count CPU cycles. Interviewers want to know whether your approach scales — and whether you can spot bottlenecks before they become bugs in production.

Big O describes how runtime grows as input size grows. It ignores constants and lower-order terms, which is why O(3n + 50) is still O(n). If you can state complexity confidently and tie it back to your code structure, you signal senior-level thinking even on medium problems.

## What Big O actually means

We write O(f(n)) to say: "For large enough input, runtime grows no faster than f(n)." The variable n almost always means the primary input size — array length, string length, number of nodes. When two inputs matter (a grid with n rows and m columns), use both: O(nm).

Interview tip: always define n out loud before analyzing. "Let n be the number of users in the feed" removes ambiguity and buys you a few seconds to think.

## Reading loops

Loops are the fastest way to estimate complexity. Count how many times the innermost work runs relative to n.

**Single pass — O(n).** One loop over the input:

```javascript
for (let i = 0; i < nums.length; i++) {
  // constant work
}
```

**Nested loops — O(n²).** Every element paired with every other element:

```javascript
for (let i = 0; i < nums.length; i++) {
  for (let j = 0; j < nums.length; j++) {
    // constant work
  }
}
```

**Triangle loop — still O(n²).** The inner loop starts at i, not 0, but you still iterate roughly n²/2 times:

```javascript
for (let i = 0; i < nums.length; i++) {
  for (let j = i + 1; j < nums.length; j++) {
    // compare pairs
  }
}
```

Rule of thumb: k nested loops that each scale with n → O(n^k). Three nested loops over n → O(n³).

## Constants do not change Big O

These loops all look different but are all O(n):

```javascript
for (let i = 0; i < 3 * n; i++) { /* ... */ }
for (let i = 0; i < n + 100; i++) { /* ... */ }
for (let i = 0; i < n; i += 2) { /* ... */ }
```

Interviewers care about growth rate, not whether you loop 2n or 5n times. Drop constants when you speak: say O(n), not O(2n).

## Multiple passes add, but watch the max

When code runs in sequential phases, the slowest phase dominates.

```javascript
function process(nums) {
  nums.forEach(() => { /* O(n) */ });

  for (let i = 0; i < nums.length; i++) {
    for (let j = 0; j < nums.length; j++) {
      /* O(n²) */
    }
  }

  nums.sort(); // O(n log n)
}
```

Total: O(n) + O(n²) + O(n log n) = **O(n²)**. The quadratic nested loop is the bottleneck. Mention that explicitly — it shows you know which line matters.

## Two inputs: use two variables

Grids, graphs, and string matching often depend on two dimensions:

```javascript
for (let i = 0; i < n; i++) {
  for (let j = 0; j < m; j++) {
    // visit cell (i, j)
  }
}
```

Complexity is **O(nm)**, not O(n²), unless m and n are the same. For a square grid, say O(n²). For comparing two strings of length n and m, many DP solutions are O(nm).

## Recursion: multiply calls × work per call

Recursive runtime = (number of calls) × (work per call, excluding deeper recursion).

**Linear recursion — O(n).** One recursive call per level:

```javascript
function countdown(n) {
  if (n === 0) return;
  countdown(n - 1);
}
```

n calls, O(1) each → O(n).

**Binary recursion — O(2^n).** Two calls branch each level (think naive Fibonacci):

```javascript
function fib(n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}
```

The call tree doubles at each level. Total calls grow exponentially — roughly O(2^n). In interviews, name this immediately and offer memoization or bottom-up DP to bring it to O(n).

**Divide and conquer — often O(n log n).** Merge sort splits in half (log n levels) and does O(n) merge work per level → O(n log n). Same pattern appears in fast FFT-style problems and some tree algorithms.

## Complexity cheat sheet for interviews

Memorize the ordering. When comparing approaches, refer to where each sits on this ladder:

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2^n) < O(n!)

### O(1) — constant

Hash map lookup, array index access, pushing to a stack. Does not grow with input size.

### O(log n) — logarithmic

Binary search, balanced BST operations, repeatedly halving the search space. If you eliminate half the remaining data each step, think log n.

### O(n) — linear

Single scan, two pointers on a sorted array, BFS/DFS when each node is visited once. Often the best you can do if you must examine every element.

### O(n log n) — linearithmic

Efficient sorting, merge sort, heap operations over n items, divide-and-conquer with linear combine step. If your solution sorts the full input, start here.

### O(n²) — quadratic

Nested loops, brute-force pair checking, simple DP on small grids. Common in naive solutions — interviewers often ask how you'd improve it.

### O(2^n) and O(n!) — exponential / factorial

Generating all subsets or all permutations. Fine for n ≤ 20 in backtracking problems; unusable at scale. Name the pattern when you see bitmask or "try every ordering" approaches.

## What interviewers want to hear

1. **State Big O for time and space** after you describe the approach — not after you finish coding.
2. **Tie complexity to a line of code** — "The nested loop over pairs gives O(n²)."
3. **Compare to alternatives** — "Sorting first is O(n log n); a hash map lookup is O(n) average."
4. **Call out trade-offs** — O(n) extra space for O(n) time is a deliberate exchange.

You do not need formal proofs. You need a consistent method: find the hot loop, count how many times it runs, express it in terms of n, drop constants, keep the dominant term.

## When your solution might be too slow

Typical online judges and interview platforms handle roughly:

- O(n) or O(n log n) — safe for n up to 10⁶ or more
- O(n²) — fine for n ≈ 10³–10⁴
- O(2^n) — only when n ≤ 20–25

If your brute force is O(n²) and constraints say n = 10⁵, stop and rethink before coding. That constraint is a hint.

## Practice on real problems

Work through the study guide on [LRU Cache](/questions/lru-cache) — every operation is O(1) and you should explain why. Then compare with [Merge Intervals from Data Stream](/questions/merge-intervals-stream), where the heap gives O(log n) per insertion.

## Related reading

- [Sorting algorithms: time complexity cheat sheet](/articles/sorting-algorithms-time-complexity) — where O(n log n) shows up in practice.

How to Analyze Time Complexity in Coding Interviews

Sorting is one of the most frequently tested topics in coding interviews. You rarely need to implement a full sort from scratch, but you must know the time and space trade-offs cold — and explain why your chosen approach fits the problem constraints.

## Why interviewers ask about sorting

- Many problems reduce to "find the k-th element" or "group similar items" — sorting is often the brute-force baseline.
- Follow-ups probe whether you know faster alternatives (heaps, counting sort, bucket sort).
- System design loops sometimes ask how databases or distributed systems sort large datasets.

## Comparison-based sorts

### Bubble Sort

O(n²) time, O(1) space. Compare adjacent pairs and swap. Simple but almost never the right answer in interviews. Mention it only to contrast with better options.

### Selection Sort

O(n²) time, O(1) space. Repeatedly pick the minimum from the unsorted portion. Still O(n²) but performs fewer swaps than bubble sort. Rarely used in practice.

### Insertion Sort

O(n) best, O(n²) average/worst, O(1) space. Builds a sorted prefix one element at a time. Excellent for nearly sorted data or small n (often n < 50). Python's Timsort uses insertion sort for small runs.

### Merge Sort

O(n log n) time in all cases, O(n) space. Divide the array in half, sort each half, merge. Stable, predictable, and great when you need guaranteed O(n log n). Downside: extra memory for the merge step.

### Quick Sort

O(n log n) average, O(n²) worst, O(log n) space for recursion stack. Pick a pivot, partition, recurse. In-place and cache-friendly — the default in most standard libraries (with randomized pivot or introsort to avoid worst case). Unstable unless implemented carefully.

### Heap Sort

O(n log n) time in all cases, O(1) space. Build a max-heap, repeatedly extract the maximum. Guaranteed O(n log n) with no extra array, but slower constants than quicksort in practice. Useful when memory is tight and you need worst-case guarantees.

## Non-comparison sorts

### Counting Sort

O(n + k) time, O(k) space where k is the range of input values. Works when values are small integers in a known range. Stable when implemented with prefix sums.

### Radix Sort

O(d · (n + k)) time where d is the number of digits/pass. Sorts digit-by-digit using a stable sub-sort (usually counting sort). Used for fixed-width integers or strings of bounded length.

### Bucket Sort

O(n) average when inputs are uniformly distributed across buckets, O(n²) worst if all elements land in one bucket. Good for floating-point values in [0, 1).

## Quick reference

Bubble Sort — O(n²) / O(1) / stable. Selection Sort — O(n²) / O(1) / unstable. Insertion Sort — O(n²) avg, O(n) best / O(1) / stable.

Merge Sort — O(n log n) / O(n) / stable. Quick Sort — O(n log n) avg, O(n²) worst / O(log n) stack / unstable. Heap Sort — O(n log n) / O(1) / unstable.

Counting Sort — O(n + k) / O(k) / stable. Radix Sort — O(n · d) / O(n + k) / stable. Bucket Sort — O(n) avg / O(n) / stable.

## The Ω(n log n) lower bound

Any comparison-based sort must make at least Ω(n log n) comparisons in the worst case. That is why merge sort, heap sort, and quicksort (average) are optimal for general comparison sorting — you cannot do better without exploiting structure in the input.

## When to say which in an interview

- Default answer for general arrays: quicksort or mergesort. Quicksort for in-place; mergesort when stability matters or worst-case O(n log n) is required.
- Small or nearly sorted input: insertion sort.
- Need top-k elements without full sort: use a min-heap of size k — O(n log k) instead of O(n log n).
- Integers in a small range: counting sort or bucket sort.
- Linked lists: mergesort is natural because merge is O(1) extra space per node (no random access needed).

## Common follow-up questions

### Why is quicksort O(n²) worst case?

Adversarial or sorted input with a bad pivot (first/last element) causes unbalanced partitions. Fix with random pivot or introsort (switch to heapsort when recursion depth exceeds a threshold).

### Is mergesort or quicksort better?

Quicksort wins on average for in-place array sorting due to cache locality. Mergesort wins when stability is required, data is linked, or you need predictable performance.

### Can you sort in O(n) time?

Only with non-comparison sorts when input has structure (bounded integer range, fixed digit count). Otherwise no — cite the comparison lower bound.

### What does JavaScript's Array.sort use?

V8 uses Timsort (a hybrid of mergesort and insertion sort), which adapts to partially ordered data.

## Practice tip

Before your next loop, pick three problems from our coding question bank and state aloud which sort (if any) you would use and why. Interviewers care less about memorizing every constant factor and more about matching the algorithm to constraints: stability, memory, input distribution, and whether you need the full sorted order or just the k-th element.

Sorting Algorithms: Time Complexity Cheat Sheet for Interviews

Object-oriented design interviews test whether you can model real-world systems with clear abstractions.

## Clarify requirements first

Start by clarifying requirements: what entities exist, what actions users perform, and what scale constraints apply. Sketch core classes and their relationships before writing code.

## Patterns interviewers look for

- Single responsibility for each class
- Encapsulation of state
- Extensibility for new vehicle types, payment methods, or notification channels

## Next steps

Practice with our OOD question bank — Parking Lot is a great starting point.

How to Approach OOD Interviews

SQL questions in SDE interviews often focus on practical analytics rather than exotic syntax.

## Core patterns to master

- Ranking with ROW_NUMBER, DENSE_RANK, and RANK
- Aggregations with GROUP BY and HAVING
- Self-joins for comparing rows within the same table
- Window functions for running totals and Nth highest values

## Practice with real problems

Our SQL question bank includes real problems like Second Highest Salary by Department — practice the pattern, then explain your indexing strategy as a follow-up.

SQL Patterns Every SDE Should Know

System design interviews reward structured thinking over memorized architectures.

## The 45-minute timeline

1. Requirements (5 min) — functional vs non-functional, clarify scope
2. Estimation (5 min) — QPS, storage, bandwidth back-of-envelope
3. High-level design (10 min) — boxes and arrows, data flow
4. Deep dive (15 min) — database choice, caching, bottlenecks
5. Wrap-up (10 min) — trade-offs, monitoring, failure modes

## Where to practice

Browse our System Design section for questions like URL Shortener with full walkthroughs.

A 45-Minute System Design Framework

Read guides to complement your question bank practice.

Interview prep guides, strategies, and deep dives.