Sorting and Binary Search Basics

Sort arrays and pairs with correct comparators, then use lower_bound and upper_bound to search sorted data in logarithmic time.

30 minCF 800–12005 interactive11 problems

Sorting

Sorting puts items in order. It costs $O(n \log n)$ , and it is often the first step of a fast solution: equal values become neighbours, the smallest and largest sit at the ends, and binary search becomes possible.

Task	C++	Java
ascending array	`sort(a.begin(), a.end())`	`Arrays.sort(a)`
descending	`sort(a.rbegin(), a.rend())`	sort, then reverse; or sort `Integer[]` with `Collections.reverseOrder()`
keep equal items in input order	`stable_sort`	`Arrays.sort` on objects, `Collections.sort`

Watch merge sort split and merge. It shows why the cost is $n \log n$ : about $\log n$ levels, each doing $n$ work.

Merge sortSplit in halves, sort each, merge two sorted halves with two pointers.

Step 1 Split in halves again and again until every piece has one value; then merge pieces back, smaller first.

1 / 22

Edit input

Input as JSON

1 of 8