Join Peggy Fisher for an in-depth discussion in this video Searching arrays, part of Learning Java (2015).
- Similar to sorting arrays, there are many different ways to search arrays. Let's start talking about a binary search. A binary search requires the list of values to already be sorted prior to searching. The binary search starts by comparing the key value you're searching for with the middle value in your array. If the value is greater than the middle value, it repeats the process with the half of the array that might still contain a match. This process continues until either a match is found or the array cannot be split any more.
Let's look at an example on how this might work. If this is my original sorted array and I'm trying to find the value three, the first time through it'll compare three to the middle. It'll say, is three greater than or less than four. In our case, it's less than, so now it takes the beginning half of the array, splits it again, but since there's only two items, it's going to compare the three to both items and find that there is a match. Now let's take a look at a program that uses a binary search.
As you can see, in this program, on line 14, I have an array declared called numbers that has some random numbers in it. I wanted to show you what would happen if you used the binary search to find a value that was in the array and also what happens if I run the binary search with a value that's not in the array. Let's scroll down to our binary search method. As you can see, the binary search method takes an array, a lower bound, an upper bound, and a key value, which is the value that we're searching for.
It starts by setting the position of where to search at the middle of the array. It adds the lower and the upper bound and divides by two. It uses a loop, a while loop, to go through and try to find a match. It checks to see if the key is less than the middle portion of the array. If it is, it resets the upper bound to be that position minus one. If it's not, it resets the lower bound to be that position plus one.
Then it goes ahead and finds the next half of the array. It continues through the while loop, and when it's done, if it did find a match, it'll print out a statement saying, "The number was found in the array at position," and it'll use the value position to show the user where it was. Otherwise, it'll print out a message saying, "Sorry, the number is not in the array." Let's run this program. As you can see, the number 30 was found in the array at position five, and then the second one, where the number was 31, it says, "Sorry, the number is not in the array." The binary search is a very efficient search, but remember, it depends on an already sorted array of values.
Okay, let's talk about another search, a linear search. Sometimes you'll see this referred to as a sequential search. The linear search starts with the first element and compares it to the key. It continues to search every element in the array. If a match is found, it returns the position of the match. If the search gets to the end of the array and did not find a match, it returns a negative one. To remember how a linear search works, I often think of a line. It starts at the beginning of the array and searches each element in the array, looking for a match.
These are two of the searches that you'll find most often when working with arrays. So take a minute to review the binary search and maybe even try a linear search on your own.
- Downloading and exploring NetBeans
- Understanding Java basics: data types, strings, arrays, and more
- Controlling flow with functions and loops
- Creating classes
- Sorting and searching arrays
- Manipulating files
- Handling errors
- Building GUIs