08 Searching Algorithms Free Online FlashCards

What does sequential search do?

Sequential search checks elements one at a time from the beginning until it finds the target or reaches the end.

Does sequential search require sorted data?

No. Sequential search works on unsorted collections because it checks each element directly.

What are sequential search’s time complexities?

For an array of size $n$, sequential search has best-case $\Theta(1)$, average-case $\Theta(n)$, and worst-case $\Theta(n)$ time.

What invariant proves iterative sequential search?

A loop invariant states that before each iteration, every position before the current index has been checked and does not contain the target.

How does binary search reduce its search space?

Binary search compares the target with a middle element, then discards the half that cannot contain the target.

What assumptions does binary search require?

Binary search requires sorted data, compatible comparisons, efficient middle-element access, stable ordering during the search, and a consistent boundary convention.

What is iterative binary search’s complexity on an array?

For an array of size $n$, iterative binary search takes $\Theta(\log n)$ time in the average and worst cases, with $\Theta(1)$ extra space.

What does binary search’s half-open interval mean?

The half-open interval $[low, high)$ includes $low$ and excludes $high$. The initial interval is $[0, \operatorname{length}(A))$.

Why compute binary search’s midpoint this way?

Use $low + (high - low) // 2$, which avoids the potential fixed-width integer overflow of $(low + high) // 2$.

Which values are checked when finding $23$ in the example array?

For $[3, 8, 12, 17, 23, 31, 44]$ and target $23$, binary search checks $17$, then $31$, then $23$.

What invariant proves half-open binary search?

For the half-open implementation, the invariant is: if the target occurs, it must occur within the current interval $[low, high)$.

How do recursive and iterative binary search differ in space?

Recursive binary search uses $\Theta(\log n)$ stack space, while iterative binary search uses $\Theta(1)$ auxiliary space.