Searching and Filtering Strings
Traversal is the process of handling a string one character at a time, from beginning to end.
A Character-by-Character Walk
When you search or filter a string, you often need to examine its characters in order. Traversal is the process of handling a string one character at a time, from beginning to end. The index tells you which character is being handled, while the loop controls when the walk begins, continues, and ends.
A correct traversal visits every character exactly once, in order, and stops when it reaches the end of the string.
The Three-Part Loop
A while-loop traversal has three essential parts. First, an index variable starts at 0, which points to the first character. Second, the loop condition checks whether the index is still within the string. Third, the index increases by 1 after the current character is processed. These parts work together: the index identifies the current position, the condition protects the boundary, and the increment moves the traversal forward.
fruit = "banana" index = 0 while index < len(fruit): print(fruit[index]) index = index + 1
Tracing Banana
Walking Through banana
Determine the characters visited by the traversal and the value of index when the loop stops.
Start: The string banana has length 6. The index starts at 0.
First iteration: The condition 0 < 6 is true. Index 0 selects b, and the index becomes 1.
Continuing iterations: Indices 1, 2, 3, 4, and 5 select a, n, a, n, and a in that order. After each character, the index increases by 1.
Final check: After index 5 is processed, the index becomes 6. The condition 6 < 6 is false, so the loop stops.
The characters are visited in the order b, a, n, a, n, a. The loop stops when index is 6.
b
a
n
a
n
aWhat do you think happens?
After the loop prints the character at index 5 in banana, what happens next?
Reveal answer
Answer: The index becomes 6 and the condition becomes false.
banana has length 6. Its valid indices are 0 through 5. Once index becomes 6, index < len(fruit) is false, so the loop stops.
The Boundary Gate
The condition index < len(fruit) is the boundary check that keeps the traversal inside the string. If a string has length 5, its valid indices are 0, 1, 2, 3, and 4. The index value 5 is the string's length, not a valid character position. Therefore, the last character is accessed at len(fruit) - 1, and the loop should stop before trying to access the length itself.
Searching and Filtering Actions
Traversal supplies the repeated movement through the string. At each index, fruit[index] gives the current character, which can then be handled by the action your task requires. For a search, the action can inspect the current character to determine whether it is the character of interest. For filtering, the action can decide whether the current character should be retained or ignored. The traversal pattern remains the same: start at 0, check the boundary, process the current character, and increment the index.
Traversal Debugging
Starting the index at the wrong position
The traversal pattern starts at 0 so that it begins with the first character. Starting at 1 skips the character at index 0.
Fix:
Set index = 0 before the loop.Using the wrong stopping condition
When index reaches the string's length, that position does not contain a character. Including it attempts to access an index that does not exist.
Fix:
Use while index < len(fruit):Forgetting to increment the index
The index must move forward after each iteration so the traversal can reach the next character and eventually stop.
Fix:
Increment the index by 1 after processing the current character.Reading the index update as happening before the current character
In the traversal pattern, the current character is accessed and processed before the index is incremented.
Fix:
Trace each iteration in this order: check the condition, access the character, process it, then increment the index.
Practice Trace
Trace the traversal for the string banana. Write down the value of index and the character accessed on each iteration. Then identify the value of index at the first condition check that is false.
Hints
- The string length is 6.
- Begin with index 0.
- The valid indices end at 5.
- The index increases after each character is processed.
Practice Check
What index values access characters in banana, and what value stops the loop?
Character positions: The character positions are 0, 1, 2, 3, 4, and 5.
Character order: Those positions access b, a, n, a, n, and a.
Stopping value: After index 5 is processed, the index becomes 6. The condition 6 < 6 is false.
The loop accesses indices 0 through 5 and stops with index equal to 6.
Key Takeaways
- Traversal handles a string one character at a time from beginning to end.
- The standard while-loop pattern starts index at 0, checks index < len(string), processes string[index], and increments index by 1.
- For a string of length 6, valid indices are 0 through 5; index 6 signals that traversal should stop.
- The condition index < len(string) prevents the loop from accessing a position that does not exist.
- Searching and filtering actions can be placed inside the traversal after the current character is accessed.
Key Takeaways
- Traversal means processing a string one character at a time in order.
- A while loop needs an index, a boundary condition, and an increment.
- The last valid index is len(string) - 1, so the loop condition should use a strict less-than comparison.
- Tracing the index before and after each iteration reveals skipped characters, invalid accesses, and missing increments.
- Searching and filtering actions can use the current character produced by the traversal.