8 Searching Algorithms Free Online FlashCards

What factors guide the choice of a search algorithm?

Search choice depends on whether data is ordered, whether elements are directly indexable, how often data changes, and what result is required.

What is linear search?

Linear search checks elements in order until it finds the target or reaches the end. It works on sorted and unsorted collections.

What prerequisites does binary search have?

Binary search requires data sorted by the same comparison rule and efficient access to a middle element, such as array indexing.

How does binary search reduce its search range?

Binary search repeatedly compares the target with the middle element and discards approximately half of the remaining candidates.

Why is binary search logarithmic?

After about $k$ halvings, roughly $n / 2^k$ elements remain; reaching one element requires $k \approx \log_2 n$.

What loop invariant proves binary search’s correctness?

The invariant states that if the target occurs, it is within the inclusive range from `low` through `high`.

Why must binary search updates exclude `mid`?

Use `mid + 1` or `mid - 1` because the comparison has established that `mid` cannot be the answer; otherwise the loop may not progress.

Why calculate binary search’s midpoint using `low + (high - low) // 2`?

`low + (high - low) // 2` reduces the risk of integer overflow compared with `(low + high) // 2` in fixed-width integer languages.

How does binary search find the first duplicate occurrence?

To find the first occurrence, record a match and continue searching the left side by setting `high = mid - 1`.

Why is binary search less effective on linked lists?

Arrays provide direct middle-element access, but linked lists require traversal; a straightforward binary-search strategy on a linked list can take $O(n \log n)$ traversal work.

What cost must be included before repeated binary searches?

Sorting may cost at least $O(n \log n)$ for comparison-based algorithms, so that preprocessing cost must be included when evaluating the complete process.

How do hash tables and balanced search trees differ for lookup?

A hash table offers expected $O(1)$ exact-key lookup, while a balanced search tree generally supports ordered searches and updates in $O(\log n)$.