Given a sorted array of integers and a target, return its index, or -1 if it is not there.

Keep low = 0 and high = n - 1. While low <= high, set mid = low + (high - low) / 2. If the item at mid is the target, return mid. If it is smaller than the target, set low = mid + 1. Otherwise set high = mid - 1. If the loop ends, return -1. Each step halves the range, so time is O(log n). The loop version uses O(1) memory (the recursive version uses O(log n) stack).

A sorted array was rotated at an unknown point, for example [4, 5, 6, 7, 0, 1, 2]. Find a target in O(log n).

Use binary search. At each step, one half (low to mid, or mid to high) is sorted: compare the item at low with the item at mid to tell which. If the target lies inside the sorted half, search that half. Otherwise search the other half. Each step halves the range, so time is O(log n) and memory is O(1). This assumes there are no duplicates. With duplicates the worst case becomes O(n).

Packages with given weights must ship in order within D days. A ship carries at most one capacity per day. Find the smallest capacity that works.

This is binary search on the answer. The smallest possible capacity is the heaviest package, and the largest needed is the total weight. For a candidate capacity, simulate loading packages in order and count the days. If it fits in D days or fewer, the answer is this or smaller, so search lower. Otherwise search higher. Each check is O(n) and there are O(log(total weight)) checks, so time is O(n log W) with O(1) extra memory.

Compare merge sort and quick sort. When would you pick each?

Merge sort is O(n log n) in every case, uses O(n) extra memory for merging, and is stable. It suits linked lists, data that must keep the order of equal items, and sorting data too big for memory (external sort). Quick sort is O(n log n) on average, sorts in place with O(log n) stack, and is usually faster in practice because it works well with the processor cache. Its worst case is O(n²) when pivots split badly, for example the last item as pivot on sorted input. Choosing the pivot randomly or by median of three makes that unlikely. It is not stable.

Sorting and Binary Search

Q: A sorted array was rotated at an unknown point, for example [4, 5, 6, 7, 0, 1, 2]. Find a target in O(log n).

Use binary search. At each step, one half (low to mid, or mid to high) is sorted: compare the item at low with the item at mid to tell which. If the target lies inside the sorted half, search that half. Otherwise search the other half. Each step halves the range, so time is O(log n) and memory is O(1). This assumes there are no duplicates. With duplicates the worst case becomes O(n).

Q: Packages with given weights must ship in order within D days. A ship carries at most one capacity per day. Find the smallest capacity that works.

This is binary search on the answer. The smallest possible capacity is the heaviest package, and the largest needed is the total weight. For a candidate capacity, simulate loading packages in order and count the days. If it fits in D days or fewer, the answer is this or smaller, so search lower. Otherwise search higher. Each check is O(n) and there are O(log(total weight)) checks, so time is O(n log W) with O(1) extra memory.

Q: Compare merge sort and quick sort. When would you pick each?

Merge sort is O(n log n) in every case, uses O(n) extra memory for merging, and is stable. It suits linked lists, data that must keep the order of equal items, and sorting data too big for memory (external sort). Quick sort is O(n log n) on average, sorts in place with O(log n) stack, and is usually faster in practice because it works well with the processor cache. Its worst case is O(n²) when pivots split badly, for example the last item as pivot on sorted input. Choosing the pivot randomly or by median of three makes that unlikely. It is not stable.

Put data in order, then find things by halving the search range. Covers merge sort, quick sort, binary search and binary search on the answer.

beginner30 minAsked oftenSortingBinary searchMerge sortQuick sortBinary search on the answer

Last reviewed 24 Oct 2026 · by TheLearningLoop Team

Read first: Data Structures & Algorithms: The Big Picture (blog post)

Progress is saved on this device. Create a free account to keep it everywhere.

On this page ▾

On this page

Key takeaways

Binary search halves the range each step, so it finds a value in a sorted array in O(log n).
Merge sort is O(n log n) in every case and uses O(n) extra memory. Quick sort is O(n log n) on average but O(n²) in the worst case.
Binary search also works on any yes or no question that flips once from no to yes, which is called binary search on the answer.

When to use sorting and binary search

Sort when you need:

Data in order for display, such as a leaderboard, a price list or search results.
Equal items next to each other, to remove duplicates, count groups or compare two lists.
To prepare for something faster: binary search, two pointers or merging all want sorted input.

Use binary search when:

You have sorted data and will search it more than once.
You want a position, not just yes or no: the first item at least x, the last item at most x, or where to insert x.
You have a yes or no question that flips once, such as "does this version work?", and want the first "yes". This is binary search on the answer.

Use something else when:

You search once in unsorted data: a plain scan is O(n), cheaper than sorting first at O(n log n).
You look up exact keys all the time: use a hash map.
The data changes constantly and must stay sorted: use a balanced tree.
You only need the smallest or largest few items: use a heap.
The keys are small whole numbers: counting sort can beat any comparison sort.

Do not write your own sort in production. Every language ships a tuned one, and a binary search is in the standard library of most (see the real-world section). Writing them by hand is for learning and interviews.

How sorting and binary search work

Binary search finds a value in a sorted list by looking at the middle first.

If the middle item is too small, everything to its left is too small as well, so discard that whole half. If it is too big, discard the right half. Repeat on what is left.

Each look throws away half of the remaining items, so 1,000 items need at most about 10 looks and a million need about 20. That is O(log n). It only works because the list is sorted.

Sorting puts items in order. Two classic methods that both beat the simple O(n²) ones:

Merge sort splits the list in half, sorts each half, then merges the two sorted halves by repeatedly taking the smaller front item. It always takes O(n log n) time, needs O(n) extra memory for the merging, and is stable (equal items keep their original order).
Quick sort picks a pivot, moves smaller items to its left and larger ones to its right, then sorts each side the same way. It is O(n log n) on average and sorts in place, but if the pivot keeps being the smallest or largest item, it falls to O(n²).

Binary search on the answer uses the same halving on a range of possible answers instead of a list. If you can test "is x big enough?" and the answer flips from no to yes just once as x grows, you can find the smallest x that works in O(log range) tests.

Try it

Pick binary search, merge sort or quick sort and step through. Watch the counters.

Sorting and binary search

Step 1 of 4 · Press Space to play, arrow keys to step

Examples:

low

high

Search for 23 in the sorted list. Look at the middle item: each look will discard half of what is left.

comparisons:: 0
linear scan would need:: 10

comparisons = times two values were compared. writes = times a value was written into the array.

Speed

Things to try:

Binary search for 23 in the sorted list. It takes 3 comparisons, where scanning from the left needs 6. Then search for 40, which is not in the list: it takes 4 comparisons to be sure.
Merge sort with Shuffled: 14 comparisons. With Already sorted: 11. It barely cares about the starting order.
Quick sort with Shuffled: 11 comparisons. With Already sorted: 21, the worst case for a last-item pivot, which is 7 × 6 ÷ 2. Quick sort is only fast when the pivot splits the data roughly in half.

Sorting and binary search operations

Binary search. Keep low and high. Look at mid. If it is the target, stop. If it is too small, set low to mid + 1. If it is too big, set high to mid - 1. If low passes high, the target is not there.

Merge two sorted halves. Keep one pointer in each half. Compare the two front items, copy the smaller into the result, and move that pointer. When one half runs out, copy the rest of the other.

Partition (quick sort). Choose a pivot. Scan through, moving each item smaller than the pivot to the left region. Put the pivot between the regions. It is now in its final position.

Binary search on the answer. Decide the range of possible answers. Write a function that says yes or no for one candidate. Search for the first yes.

Three bugs to avoid: use mid = low + (high - low) / 2 so the sum cannot overflow, decide whether the loop is low <= high or low < high and keep your updates consistent with it, and make sure each step really shrinks the range, or the loop never ends.

Interview fact. Comparison-based sorting cannot be faster than O(n log n) in the worst case. Binary search is O(log n), but only on sorted data, so sorting first adds O(n log n).

Sorting and binary search time complexity

Algorithm	Best	Typical	Worst	Extra memory
Binary search (loop version)	O(1)	O(log n)	O(log n)	O(1)
Merge sort	O(n log n)	O(n log n)	O(n log n)	O(n)
Quick sort	O(n log n)	O(n log n)	O(n²)	O(log n) stack
Heap sort	O(n log n)	O(n log n)	O(n log n)	O(1)
Insertion, bubble and selection sort	O(n) or O(n²)	O(n²)	O(n²)	O(1)

Stable sorts keep equal items in their original order: merge sort is stable, quick sort and heap sort are not (in their usual forms). Stability matters when you sort by one field and then by another.

Sorting and binary search vs other approaches

The right choice depends on what you do most. n is the number of items and k is the number of results returned.

What you need	Sorted array + binary search	Unsorted scan	Hash map	Balanced tree
Find a value	O(log n)	O(n)	O(1) average	O(log n)
Insert a new value	O(n)	O(1) at the end	O(1) average	O(log n)
Range query ("between a and b")	O(log n + k)	O(n)	O(n)	O(log n + k)
Nearest value (floor or ceiling)	O(log n)	O(n)	O(n)	O(log n)
Set-up cost	O(n log n) to sort once	None	O(n)	O(n log n)
Memory	O(n), compact	O(n), compact	O(n) plus spare slots	O(n) plus pointers

The bold cells show where each wins. A sorted array with binary search is the best for data that is built once and queried many times. It is the worst when you insert often, because each insert shifts the items after it.

How to explain sorting and binary search in an interview

Say the precondition: "binary search needs sorted data, or a yes or no test that flips once."
Give the cost: "O(log n) per search, and O(n log n) to sort first, so it pays off over many searches."
Compare sorts in one line: "merge sort is always O(n log n) but uses O(n) memory, quick sort is O(n log n) on average, O(n²) in the worst case, and sorts in place."
Mention stable when the question sorts by more than one field.
Name how you avoid off-by-one mistakes: the loop condition, the way mid is computed, and that every step shrinks the range.

Where you meet sorting and binary search in real systems

Sorted data and halving searches sit inside databases, version control and every language's standard library. Here are three drawn out, the first with code you can run, then more examples.

Example 1: Finding the commit that broke the build

You know commit 1 worked and commit 100 is broken, and you want the first bad commit. Checking all 100 would take 100 builds. But history is like a sorted list of "good, good, ..., bad, bad", so you can test the middle commit and discard half the range each time. git bisect does exactly this: for 100 commits it needs at most 7 tests. Open the example below to see the picture and the code.

Code: find the first bad commit with binary searchTime O(log n)Memory O(1)

Commits 1 to 6 are good and 7 to 10 are bad. Test commit 5: good, so discard 1 to 5. Test commit 8: bad, so keep 6 to 8. Test 7: bad, so keep 6 to 7. Test 6: good, so 7 is the first bad commit. Four tests instead of ten.

def first_bad_commit(n, is_bad):
    """Find the first bad commit among commits 1..n using binary search.

    This is the idea behind `git bisect`. Commits before the bug are good and
    every commit from the first bad one onwards is bad, so the history is
    "sorted" as good, good, ..., bad, bad. `is_bad(c)` builds and tests commit c.

    Time:   O(log n) calls to is_bad. Each test halves the range of commits left.
    Memory: O(1). Only the two ends of the range are stored.
    """
    low, high = 1, n                      # the first bad commit is somewhere in [low, high]
    while low < high:
        mid = (low + high) // 2           # test the middle commit
        if is_bad(mid):
            high = mid                    # mid might be the first bad one: keep it
        else:
            low = mid + 1                 # mid is good, so the bug came later
    return low                            # one commit left: the first bad one

Each version searched commits 1 to 100 with a test that says "bad" from commit 37 onwards, and printed 37 7: the first bad commit is 37, found with 7 tests. All five were compiled and run, and none of them uses a package.

Example 2: Sorting more data than fits in memory

A database sorting a huge table for ORDER BY cannot always hold it all in memory. It uses an external merge sort: read chunks that fit in memory, sort each chunk and write it out as a sorted "run", then merge the runs together. Merging only needs the front of each run, so very little memory is used.

Each chunk is sorted in memory and saved as a sorted run. Merging the runs reads them front to back, so memory use stays small however big the file is.

Example 3: Looking up a name in an index

A phone book is sorted, so you open it near the middle, see whether your name is before or after, and repeat on that half. Database indexes work the same way: inside each page of a B-tree index the keys are sorted, and the database uses binary search to find the right key quickly.

Look at the middle, 16, and discard the left half. Look at 56, and discard the right. Look at 23: found. The list shrinks 10, then 5, then 2 items.

More real-world scenarios

4. Leaderboards and ranked lists

A leaderboard is a list sorted by score. Sorting once gives the order, and binary search on the sorted scores answers "what rank would a score of 1,200 have?" in O(log n).

5. Large-scale data processing

Frameworks that process huge data sets, such as Hadoop MapReduce, sort records by key between stages so that all records with the same key end up next to each other and can be handled together.

6. Capacity planning with binary search on the answer

"What is the smallest number of servers that keeps latency under the limit?" If adding servers never makes latency worse, the answer is monotone. You can test a candidate, then halve the range of candidates, instead of trying every number.

7. Sorting tables by more than one column

When you click one column in a table and then another, the order of the first sort is kept for ties only if the sort is stable. That is why many libraries guarantee stability, or offer a stable variant.

8. Drawing order in graphics

Some rendering methods, such as the painter's algorithm, sort objects from farthest to nearest and draw them in that order, so nearer objects cover farther ones.

9. Looking up lines in sorted log files

Log files written in time order are sorted by timestamp. A tool can binary search by time to jump to the first line after a given moment instead of reading the whole file. The Unix look command does the same for sorted word lists.

10. Deduplicating and grouping

After sorting, equal items sit next to each other. That makes it easy to remove duplicates, count how many of each there are, or compare two lists in one pass.

Language standard libraries

Every mainstream language sorts for you. Most also have a binary search.

Language	Structure or class	What it is under the hood	Notes
Java	`Arrays.sort`, `Collections.sort`, `Arrays.binarySearch`	Dual-pivot quicksort for primitive arrays, TimSort (a merge sort variant) for objects	Object sorting is stable.
C++	`std::sort`, `std::stable_sort`, `std::lower_bound`	`sort` is usually introsort (quick sort with fallbacks)	`lower_bound` gives the first item not less than a value.
C#	`Array.Sort`, `List<T>.Sort`, `Array.BinarySearch`	Introsort	Not stable.
Rust	`slice::sort`, `sort_unstable`, `binary_search`, `partition_point`	`sort` is stable. `sort_unstable` is faster and does not keep order of equals	`partition_point` does binary search on a yes or no test.
Python	`sorted`, `list.sort`, the `bisect` module	Timsort	Stable. `key=` sorts by a field. `bisect` does binary search.
Go	`slices.Sort`, `sort.Slice`, `slices.BinarySearch`, `sort.Search`	Pattern-defeating quicksort	`sort.Search` does binary search on a yes or no test.
JavaScript	`Array.prototype.sort`	A stable sort in modern engines	With no function it compares items as text, so `[10, 9, 1].sort()` gives `[1, 10, 9]`. There is no built-in binary search.
Kotlin	`sorted()`, `sortedBy`, `binarySearch()`	Uses Java's sorting	Stable for objects.

The pattern: you almost never write a sort yourself. Several languages also expose "binary search on a yes or no test" (partition_point, sort.Search), which is exactly binary search on the answer.

The takeaway

Whenever a system needs items in order, or the first item that passes a test, in a big collection, look for sorting plus binary search. When it only needs exact-match lookups, it usually uses a hash map instead.

Interview questions

Try answering out loud before you reveal hints. Interviewers care about how you reason, not just the final answer.

1.
Given a sorted array of integers and a target, return its index, or -1 if it is not there.
easy
2.
A sorted array was rotated at an unknown point, for example [4, 5, 6, 7, 0, 1, 2]. Find a target in O(log n).
medium
3.
Packages with given weights must ship in order within D days. A ship carries at most one capacity per day. Find the smallest capacity that works.
medium
4.
Compare merge sort and quick sort. When would you pick each?
medium

← Previous

Two Pointers and Sliding Window

Trees