Search and stop: conditional termination

In Week 1 we usually visited every card. Sometimes the question only asks whether any matching card exists. Once you find one, further searching cannot change the answer “yes”, so you can stop early.

Use a Boolean flag to remember success #

Initialize Found to False. For each card, test the required condition. When it matches, save any needed result and set Found to True. Include NOT Found in the loop’s continuation condition. The procedure then leaves through its normal loop test rather than a confusing side arrow.

Found = False
Result = NONE
while (Pile1 has cards AND NOT Found) {
    Read a card X
    Move X to Pile2
    if (X matches the condition) {
        Found = True
        Result = X.CardNo
    }
}
Report Found and Result

Example: above 90 in every subject #

The condition is Mathematics > 90 AND Physics > 90 AND Chemistry > 90. A mark of exactly 90 fails “above 90”. In the supplied Scores table, Rahul on card 11 has 97,92,92 and meets the condition. Save the ID as well as the flag if you need to identify the student.

If the first test of an AND is false, you already know the whole condition is false. You can skip the remaining tests for that card. This does not mean skipping the handling needed to mark the card visited.

Know what question you are answering #

Read the exit state #

Found True means the procedure found a match. Found False after the pile is exhausted means none matched. An empty initial pile leaves Found False and Result NONE. Remaining unvisited cards after a successful search are expected; do not claim they were all examined.

Source: Lecture 2.1 — Conditional termination in iteration. Small teaching datasets and diagrams are prepared for these notes; lecture and tutorial totals are identified explicitly.