4.12 Binary Searching with Arrays

You want to search an array for a specific item using a binary search method.

Technique

The Array and ArrayList classes each contain a method named BinarySearch . This method contains several overloads, which allows you to choose the best method to perform the search. To search an entire array for a specified object, call the static BinarySearch method, passing a single-dimension array and the object to search for:

 Array.BinarySearch( myArray, "my value" ); 

You can also limit the search to a specific range by specifying a starting index and the number of items to search in:

 Array.BinarySearch( myArray, 2, 3, "my value" ); 

You can also control how the comparison between objects is performed by passing an object in the last parameter that implements the IComparer interface. This interface contains a single method named Compare with two objects as parameters. This comparer can be either a .NET Framework comparer such as the CaseInsensitiveComparer class or one created by you. The previous recipe contains an example showing how to create your own comparer:

 Array.BinarySearch( myArray, "My Value", new CaseInsensitiveComparer() ); 

Comments

Performing a linear search is a time-consuming process. Linear searching starts at the first index of a collection and checks the value of each index until the value you are searching for is found. For large arrays, this type of search can take a considerable amount of time. Binary searching drastically cuts the time it takes to search for a value. Binary searching works only on a sorted array. Therefore, when you want to perform a binary search using the BinarySearch method, you must ensure that the array is sorted. You can do so by calling the static method Sort , which takes the array to sort as a parameter.

Binary searching works well because it reduces the number of elements it takes to find a value. It begins by finding the middle element of the array. If the value it is searching for is less than that middle value, you are guaranteed that the value is not in the upper half of the array, which means you don't have to search any of those values. The search then finds the middle index of the lower half and compares it with the target value. Again, if the value is lower than the middle index, it searches the lower subarray; otherwise , it searches the upper subarray. This process repeats until the value is found. Because you effectively cut the search space in half each time, which is why it is called a binary search, the performance runs in O(log ₂ n ) time. Listing 4.6 shows how to create a simple number-guessing game utilizing a binary search to determine whether the user has made successful matches.

Listing 4.6 Performing a Binary Search on an Array of Integers

 using System; using System.Collections; namespace _12_BinarySearch {     class Class1     {         [STAThread]         static void Main(string[] args)         {             int[] lottoNumbers = new int[3];             // generate the random numbers             GenerateNumbers( lottoNumbers );             // start the game             PlayGame( lottoNumbers );         }         static void GenerateNumbers( int[] numbers )         {             // initialize random number generator with current ticks             Random rand = new Random((int)DateTime.Now.Ticks);             // fill array with random numbers from 1 to 10             for( int i = 0; i < numbers.GetUpperBound(0)+1; i++ )             {                 numbers[i] = rand.Next( 1, 10 );             }             // sort the final array             Array.Sort( numbers );         }         static void PlayGame( int[] numbers )         {             int[] playerNumbers = new int[3];             char[] space = {' '};             string input;             int matches = 0;             // get user input and quit if 'q' is entered             Console.Write( "Enter 3 digits between 1 and 10 (q to quit): " );             input = Console.ReadLine();             while( input.Length != 1  Char.ToUpper( input[0] ) != 'Q' )             {                 // split the input into a string array                 string[] temp = input.Split( space, 3 );                 // make sure 3 numbers were entered                 if( temp.Length < 3 )                 {                     Console.WriteLine( "You did not enter 3 digits." );                     Console.Write( "Enter 3 digits between 1 and 10 " +                         "(q to quit): " );                     input = Console.ReadLine();                     continue;                 }                 // convert string values and place into integer array                 for ( int i = 0; i < 3; i ++ )                     playerNumbers[i] = Int32.Parse( temp[i] );                 // count how many matches occured                 matches = NumMatches( playerNumbers, numbers );                 if( matches == 3)                 {                     Console.WriteLine( "You won!" );                     return;                 }                 else                 {                     Console.WriteLine( "You have {0} matches. Try again.",                         matches );                 }                 Console.Write( "Enter 3 digits between 1 and 10 " +                     "(q to quit): " );                 input = Console.ReadLine();             }         }         static int NumMatches( int[] playerNumbers, int[] numbers )         {             int matches = 0;             // arraylist to hold current numbers to compare             ArrayList al = new ArrayList( numbers );             foreach( int number in playerNumbers )             {                 // search for current user number in arraylist                 int result = al.BinarySearch( number );                 if( result >= 0 )                 {                     // since matched, remove it so it isn't counted again                     al.RemoveAt( result );                     matches++;                 }             }             return matches;         }     } } 

Listing 4.6 shows how binary searching works with an array of integers. The application is a number-guessing game that uses an array of three integers from 1 to 10. The numbers are generated randomly using the Random class, which itself is seeded based on the current date and time. Once the array is created, the game begins. The user must enter three digits. Those three digits are then placed in an array, which is enumerated. For each value in that array, the program performs a binary search on the target numbers and keeps a count of matches. If there are three matches, the user guessed the numbers and the game is over. Figure 4.6 shows an example of running this application.

Figure 4.6. An array of integers is searched using a binary search to determine whether a successful match occurs.