Searching

Minimum and maximum

How many comparisons do you need to find the minimum of an array of length $n$? What about the maximum? What if you need both?

Binary search

You are given an array and asked to check if a given element appears in it. What is the time complexity of your solution? How would you answer change if the input array is sorted?

Intersecting sorted arrays

You are given two sorted arrays $A$ and $B$ and asked to compute their intersection $C$, an array containing all elements that appear in both $A$ and $B$ and if free of duplicates. Let $a$ and $b$ be the lengths of $A$ and $B$ respectively. What is a good way to find $C$ if $a \approx b$? What if $a \ll b$ or $a \gg b$?

Sorted matrix search

We call a matrix sorted if each of its rows and columns is sorted. What is the fastest way to check if a sorted matrix contains a given value?