Searching CS Thinking Example 2

Follow the full solution, then compare it with the other examples linked below.

Example 2

medium
Use binary search to find 23 in the sorted list [5, 10, 15, 20, 23, 30, 35]. Show each step.

Solution

  1. 1
    Step 1: Low=0, High=6, Mid=3. List[3]=20. 23 > 20, so search right half: Low=4, High=6.
  2. 2
    Step 2: Mid=5. List[5]=30. 23 < 30, so search left half: Low=4, High=4.
  3. 3
    Step 3: Mid=4. List[4]=23. Found! 3 comparisons.

Answer

Found at index 4 after 3 comparisons.
Binary search halves the search space each step by comparing with the middle element. It requires a sorted list but is much faster than linear search: O(log⁡n)O(\log n).

About Searching

The process of locating a specific item or value within a collection of data using a systematic strategy. The two fundamental approaches are linear search (check every element one by one) and binary search (repeatedly halve the search space in sorted data).

Learn more about Searching →

More Searching Examples

Example 1 medium

Use linear search to find the value 7 in the list [3, 9, 7, 1, 5]. How many comparisons are needed?

Example 3 medium

Can binary search be used on the unsorted list [8, 2, 5, 1, 9]? Why or why not?

Example 4 hard

A sorted list has 128 elements. In the worst case, about how many comparisons does binary search nee

← All Searching Examples Searching Concept