Search That Never Terminates
A student writes a linear search to find a target value in a list of 10,000 unsorted numbers. The loop is written as: start at index 0, and while list[i] != target: i = i + 1. When the target is present, the program works. When the target is absent, the program crashes after running past the end of the list. The student also wants to know whether switching to binary search would help, but the list is unsorted and is rebuilt in a different order each day.
1. Identify the flaw in the loop and explain the two conditions a correct linear search must check on every iteration.
Read the worked answer
The loop only checks one condition: whether the current element equals the target. It never checks whether the index has run past the end of the list, so when the target is absent the index keeps growing until it indexes out of bounds.
A correct linear search must check two conditions each iteration:
iis still a valid index (i < length), andlist[i]is not the target.
The loop continues only while both hold. After the loop, a separate check decides the result: if i < length, the target was found at i; otherwise it is absent. The bug is a missing termination condition - the loop has no guaranteed stopping point for the not-found case.
2. The student asks whether binary search would be faster. Advise, given the list is unsorted and reshuffled daily.
Read the worked answer
Binary search cannot be used as-is. It requires the data to be sorted, because each step discards half the list based on an ordering comparison. On an unsorted list, discarding half would risk discarding the target.
The options are:
- Sort once, then binary search repeatedly. Sorting 10,000 items costs roughly n log n; each binary search then costs about log n. This pays off only if you search many times between rebuilds.
- Keep linear search if searches are few. Linear search is O(n) but needs no preparation.
Since the list is rebuilt in a different order each day, the sort cost is paid daily. If there are many searches per day, sort-then-binary-search wins; if only a handful, plain linear search is simpler and cheaper overall. The decision is about total work, not the speed of a single search.