A common programming task is to search through a list of data for a specific value. The list might be a list of names , phone numbers, part numbers , or any one of a thousand other possibilities. Quite often, the reason for the search is to get a piece of information that can be used to find additional information associated with the list. For example, a list of names might have an account number tied to it, which then opens the door into a database. Therefore, because list searching is often the front end for other aspects of a program, we want it to be as efficient as possible. Volumes have been written on how to organize and structure data. For the moment, we'll examine only two very simple ways to search data: a sequential search and a binary search. ## Sequential SearchThe simplest method for search a list of data is to start at the first object in the list and compare it to the object you're looking for. If they match, you're done. If they don't match, you look at the next object for a match. This process of starting at the beginning of the list and proceeding through the list on a one-by-one basis is called a sequential search. Clearly, if you get lucky using a sequential search, you could find the object on the first try. If you're unlucky, you might find it after looking at every object in the list. On average, a sequential search will examine N /2 objects in a list of N objects before finding a match. Therefore, if you have 100 objects in the list, on average, you'll look at 50 items to find a match. Although this works, it isn't very efficient. ## Binary SearchA binary search of a list of data is much more efficient. That's the good news. The bad news is that a binary search requires that the list being searched be in sorted order. To understand how a binary search works, suppose that your friend wants you to guess a number he has in mind that's between 1 and 100. What's the best way to find the number in the fewest guesses? We'll assume that your friend will tell you if your guess is too high, too low, or the correct number. To illustrate , let's assume that your friend is thinking of the number 77. You should guess 50 on your first try. Your friend responds, "Too low." You now can eliminate half of the numbers in the list because the number must fall between 51 and 100. (We'll assume that your friend doesn't lie.) With your next guess, you should again try to eliminate half the list, so you would guess 75. Your friend would again respond, "Too low." You now know the number falls between 76 and 100. Again picking the midpoint of the numbers that remain , you guess 88. This time, the response is, "Too high." You now know the number falls between 76 and 87. Picking the next midpoint yields a guess of 81. The response is, "Too high." The value must fall between 76 and 80. Again selecting the midpoint, you try 78 and the response is, "Too high." Now you know the number is either 76 or 77. You try 77 and get the correct value. This process of dividing the range in half with each guess is called a binary search. Notice how you were able to zero in on the number with only 6 guesses. If you had used a sequential search, you would have had to make 77 guesses to find the number. When the length of the list is in the thousands or millions of items, the performance gain for the binary search is significant. Let's take a closer look at the binary search process. Given that our program already sorts the data, let's extend the program to perform a binary search. We need to add a few more objects to our form, as shown in Figure 14.6. ## Figure 14.6. Form and objects for the binary search program.
We added a new label named Visual Basic .NET provides a binary search method that you can use on data arrays. Listing 14.4 shows the code for the program. ## Listing 14.4 Complete Code Using the |

Visual Basic .NET Primer Plus

ISBN: 0672324857

EAN: 2147483647

EAN: 2147483647

Year: 2003

Pages: 238

Pages: 238

Authors: Jack Purdum

Similar book on Amazon

flylib.com © 2008-2017.

If you may any questions please contact us: flylib@qtcs.net

If you may any questions please contact us: flylib@qtcs.net