Introduction to Searching Algorithms

Searching is one of the most fundamental tasks in computer science. Whether you are looking for a specific contact in your phone, a song in a playlist, or a single value in a massive database, you are using a searching algorithm. In AP Computer Science A, we focus on two primary methods for finding a target value within a collection of data: Linear Search and Binary Search. Don't worry if these sound technical! At their heart, they are just two different strategies for finding what you need—one is like looking through a messy drawer, and the other is like using a dictionary. Linear Search (sometimes called sequential search) is the most straightforward way to find an item. You start at the very beginning of the list and look at every single element, one by one, until you either find the target or run out of elements.

How it Works

Imagine you have an array or an ArrayList of numbers. To perform a linear search: 1. Start at index \( 0 \). 2. Compare the element at the current index to your target value. 3. If they match, you found it! Return the current index. 4. If they don't match, move to the next index (\( i+1 \)). 5. Repeat until the end of the collection. If you reach the end without a match, return \( -1 \) to show the item wasn't found.

Key Characteristics of Linear Search

  • Order Doesn't Matter: Linear search works on any list, whether it is sorted (in order) or unsorted (random).
  • Efficiency: In the worst-case scenario (where the item is at the very end or not there at all), you have to check every single element. If there are \( n \) elements, you might perform \( n \) comparisons.
Quick Takeaway: Linear search is simple and reliable, but it can be slow for very large data sets. Binary Search is a much faster "divide and conquer" algorithm. Instead of checking every item, it eliminates half of the remaining possibilities with every single step.

The "Golden Rule" of Binary Search

There is one huge requirement for Binary Search: The data MUST be sorted. If the data is not in order (like alphabetically or from smallest to largest), binary search will not work.

How it Works (The "High-Low" Game)

Think of the game where you guess a number between \( 1 \) and \( 100 \). If you guess \( 50 \) and I say "Higher," you instantly know the answer isn't \( 1 \) through \( 50 \). You just eliminated half the numbers! 1. Start in the middle of the sorted collection. 2. If the middle element is your target, you're done! 3. If your target is smaller than the middle element, ignore the right half. 4. If your target is larger than the middle element, ignore the left half. 5. Repeat the process with the remaining half until you find the target or have no elements left to check.

Visualizing the Steps

Imagine searching for the number \( 7 \) in this sorted array:
[ \( 2, 4, 7, 10, 15, 20, 25 \) ]

1. The middle element is \( 10 \). 2. Is \( 7 < 10 \)? Yes. So, we ignore \( 10, 15, 20, 25 \). 3. Now we look at [ \( 2, 4, 7 \) ]. The middle is \( 4 \). 4. Is \( 7 > 4 \)? Yes. So, we ignore \( 2, 4 \). 5. The only element left is \( 7 \). Target found! Did you know? Binary search can be written using iteration (loops) or recursion. You will explore the recursive version more deeply in the "Recursive Searching" chapter!

Comparing Efficiency (Informal Run-Time Analysis)

On the AP Exam, you will be asked to compare how "fast" algorithms are. We do this by counting statement executions—essentially, how many times the code inside a loop runs.

Linear Search Performance

If you have a list of \( n \) items:
  • Best Case: \( 1 \) comparison (target is at index \( 0 \)).
  • Worst Case: \( n \) comparisons (target is at the end or missing).

Binary Search Performance

Binary search is much more efficient because it cuts the search area in half every time.
  • Best Case: \( 1 \) comparison (target is exactly in the middle).
  • Worst Case: For \( n \) elements, the number of steps is roughly \( \log_{2}(n) \).
Example: If you have \( 1,000 \) items, Linear Search might take \( 1,000 \) steps. Binary Search will take at most about \( 10 \) steps. That is a massive difference!

Common Mistakes to Avoid

  • Forgetting to Sort: If you try to use Binary Search on an unsorted list, your result will be wrong. Always check if the data is sorted first!
  • Off-by-One Errors: When calculating the "middle" index in Binary Search, remember that Java integer division truncates. \( (low + high) / 2 \) is the standard way to find the midpoint.
  • Return Values: Both algorithms typically return the index where the item was found, not the item itself. If the item is missing, they return \( -1 \).

Key Summary Table

Linear Search
- Data Requirement: None (works on any list).
- Logic: Check every element in order.
- Efficiency: Roughly \( n \) steps.

Binary Search
- Data Requirement: Must be sorted.
- Logic: Start at middle, eliminate half.
- Efficiency: Much faster (roughly \( \log_{2}(n) \) steps).

Check Your Understanding

Try to answer these mentally: 1. If you are searching for a name in a phone book (which is alphabetical), which algorithm is better? 2. If you have an unsorted ArrayList of random high scores, can you use binary search? 3. What value is usually returned if a searching algorithm cannot find the target? (Answers: 1. Binary Search, because it's sorted! 2. No, not unless you sort it first. 3. \( -1 \).)