ARRL - Searching (Lesson)
Searching (Lesson)
Introduction
Have you ever looked a name up in the phonebook? Did you start with the first page or did you jump to the middle and search from there? Obviously, it is more efficient to start in the middle and then move forward and backward from there. In this lesson you will learn to use different searching techniques and when each one would be useful.
Searching
Now that we are familiar with arrays, we need to be able to search for elements within them.
Let’s imagine that we need to look up John McPhail in the phonebook. No using the internet. You must get a good old fashion phonebook and find McPhail’s phone number. Ok, this won’t be too bad. The phonebook is written in alphabetical order. What method will you use to get to the M section?
There are two ways to search, sequentially or using a binary search. Most people use something like the binary search method or some combination of the two.
Sequential (or Linear) Search
The sequential search method is when you start at the beginning and look through every element one at a time until you reach the element you are looking for. In our phonebook example, a sequential search would mean we start at the beginning with the letter A and flip through one page at a time until we reach McPhail. This is not a very efficient method for searching in a phonebook.
The best-case scenario for a sequential search is that the element that we are looking for is at the beginning. The worst-case scenario is that the element we are looking for is the last element. This is an effective search if the elements are not sorted. Imagine a phonebook that was not printed alphabetically. How would you find McPhail if all the names were randomly listed?
Think about playing a guessing game. I am thinking of a number between 1-10. Using a sequential search, your guesses would be 1, 2, 3, …until you reached my number.
Binary Search
I am thinking of a number between 1 – 10. I will tell you if your guess is too high or too low, so you can adjust your next guess. How many guesses will it take to guess my number? To guess efficiently, your first guess should be 5. Based on my response you know which half of the data my number lies in. You can then guess the middle number again. Odds are, this method of searching will be faster than the sequential search.
A binary search is when you look at the element in the middle and check to see if the element you are looking for is higher or lower (before or after). If this element is greater than what we are looking for, we use the first half of the array. Then use this approach again. If it is less than the element we want, use the second half of the array. This type of search requires your data to be sorted. This is a divide and conquer method!
In our phone book search, trying to find McPhail, I would open the phonebook in the middle and hopefully land in the M section. This has gotten me much closer to what I am looking for on my first guess.
Check out this binary search demonstration:
Click on "Runestone Academy" below to open the required reading that is listed.
Runestone Academy: AP CSA – Java Review Links to an external site.
Links to an external site. READ: 13 – Searching and Sorting
Challenge Activity
Practice-It! Practice
1. Go to the PracticeIt website Links to an external site..
2. Log into account.
3. Click on Start Practicing!
4. Go to the most recent edition.
5. Click on Chapter 13: Searching and Sorting
6. Complete Self-Check: 13.2, 13.21, & 13.22
IMAGES CREATED BY GAVS