08. Searching Algorithms Free Online FlashCards

What is linear search?

Linear search checks elements one at a time until it finds the target or reaches the end. It does not require sorted data.

What is binary search?

Binary search repeatedly compares the target with the middle element and discards the half where the target cannot occur.

Does linear search require sorted data?

No. Linear search works whether or not the collection is sorted.

What ordering requirement does binary search have?

Yes. Binary search requires the data to be sorted according to the same ordering used for comparisons.

What are linear search’s best- and worst-case times?

Linear search has best-case time O(1), when the first element matches, and worst-case time O(n), when the target is last or absent.

What are binary search’s best- and worst-case times?

With efficient indexed access, binary search has best-case time O(1) and worst-case time O(log n).

What invariant does binary search maintain?

Before each binary-search step, if the target exists, it must lie between low and high. Updates remove impossible positions while preserving that possibility.

How does binary search handle target < middle value?

For an ascending list, if the target is smaller than the middle value, set high to middle - 1 and search the lower half.

How does binary search handle target > middle value?

For an ascending list, if the target is larger than the middle value, set low to middle + 1 and search the upper half.

Why use low + (high - low) // 2 for the midpoint?

The expression low + (high - low) // 2 can avoid integer overflow that may occur with (low + high) // 2 when index values are very large.

How can binary search find the first or last duplicate?

Ordinary binary search may return any matching occurrence. To find the first, record a match and continue in the lower half; to find the last, continue in the upper half.

Which boundary cases should binary search handle?

A robust binary search must handle an empty list, targets outside the data range, matches at either boundary, and absent targets.