Java

Binary Search in Java

Searching an array for the position of a value, and sorting the array, are two different processes. Searching means verifying if a value called the key, is found in the array. Sorting means putting all the values in the array in a particular order (ascending or descending). If an array is not sorted and searching is required, then the program has to start from index zero, then to index 1, then index 2, and so on, until it reaches the index of the value it is looking for. If the value occurs more than once, the first index should be returned.

If the array is sorted first, say in ascending order, then searching becomes easy. The index is either less than the index for the middle element, if the key is less than the value of the middle index, or the index is equal to or greater than that of the middle index, if the value is equal to or greater than that of the middle index value.

So just split the array into two. If the value lies on the left side, no need to waste time searching the right side; just search the left side. If the value lies on the right side, no need to waste time searching the left side; just search the right side. Since the array is already sorted completely, when either side is arrived at, it is split again into two, and only one of the new pairs of sides is searched. In fact, searching this way is just by splitting into two, until the index of the value is arrived at. No actual search in terms of scanning takes place because the array is already sorted. There may be some slight moving right, and some slight moving left in the array during the search.

Binary implies, two. And so this kind of searching is called binary searching. There are different sorting orders: All the values in the array can be sorted in ascending order or descending order completely. An array can also be sorted in what is known as Binary Search Tree format. This is not complete sorting in ascending or descending order. However, the binary algorithm search still works with this format.

This article explains Java Binary Search. Binary search algorithm in Java works on an array that is already sorted. Only complete sorting in ascending order is considered in this article. This article begins with illustration of the binary search algorithm. It then goes on to explain how to use the binarySearch() methods of the Java Arrays class.

Article Content

Illustration of Binary Search Algorithm

Consider the following sequence of characters:

    P  V  D  Q  S  X  T  H  N  O

Arranging in ascending order, the sequence becomes:

    D  H  N  O  P  Q  S  T  V  X

There are ten elements here. Index counting begins from 0. When the number of elements is even (e.g., 10), the index for the middle element is considered as the number of elements divided by two. In this case, 10 / 2 is 5. When the number of elements is odd, the index for the middle element is taken as the integer part (whole number) of the number of elements divided by two.

There are two lists above. The second one is the sorted form of the first one. Assume that the search was to know if S was present in the first list. The list would first have to be sorted to have the second list in the binary search scheme. In the sorted list, the index for the middle position is 5 = 10 / 2. This corresponds to the value, Q. The search then stops to check if Q is S, the value looked for. If it is, then the search stops. If it is not, then the search checks if S lies less than Q or from Q upwards.

In this case, it lies in the range from Q upwards, which is then chosen. No time will be wasted searching the lower half of the list (array). So, this new range has to be divided into two. This range consists of 5 elements. 5 / 2 = 2 and a 1/2. The middle element is at position 2 of this new range. This corresponds to T, if counting from zero is to begin from Q. The actual index of T is 7.

The lower or left range now consists of (Q S), while the new upper or right range now consists of (T V X). Is the new middle element, T the same as S, the value looked for? – No. In which range does S lie; is it in the lower range, (Q S) or in the upper range, (T V X)? – It lies in the lower range.

So, the lower range (Q S) then has to be divided into two. When this is done, the middle index for this range corresponds to S (2/2 = 1, as Q is at new index 0). The actual index for S is 6 (D is at the original index 0). The index of the value found should be returned.

Key Not Found

The value looked for is called the key. The sorted list actually has two indexing as shown below:

D H N O P Q S T V X
0 1 2 3 4 5 6 7 8 9
-1 -2 -3 -4 -5 -6 -7 -8 -9 -10

The first row of this table has the sorted list. The second row has the normal indexing. The third row has a kind of negative indexing where the first element is at index -1, the second is at index -2, the third at index -3, and so on.

If the key is found, the Java algorithm will return the normal index, beginning from 0. If the key is not found, the Java algorithm will return the negative index for the position the key would have occupied (assuming that the array extended to the right by one element).

Java Package and Class for Binary Search

The java binary search scheme operates on an array that is already sorted. The Java class Arrays, which is in the java.util.* package, has binarySearch() methods for binary searching an array that is already sorted. Each of these methods returns an integer which is a normal index if the key is found, or a negative index, as explained above, if the key is not found. Two of these methods are for chars.

Constructing the Array for Search

The second list above will be used to illustrate binary search coding in Java. The following statement can be used to construct the sorted array:

            char[] arr = new char[] {'D', 'H', 'N', 'O', 'P', 'Q', 'S', 'T', 'V', 'X'};

The java binary search scheme operates on a list that is already sorted.

Binary Search Methods of the Arrays Class

The above array of chars will be used in this section for illustration. The binary search methods are in the Arrays class of the java.util.* package. This package must be imported in order for the Arrays class to be used.

All the methods of the Arrays class are static methods. This means that an object does not have to be instantiated for any of its methods to be used. Two of these methods are binary search methods for chars. The syntax of one of the binary search methods, for chars is:

    public static int binarySearch(char[] a, char key)

The following program searches for S that is found:

    import java.util.*;

    public class TheClass {

        public static void main(String[] args) {

            char[] arr = new char[] {'D', 'H', 'N', 'O', 'P', 'Q', 'S', 'T', 'V', 'X'};

            int ret = Arrays.binarySearch(arr, 'S');

            System.out.println(ret);

        }

    }

The output is 6. The following code segment searches for B, U and Z that are each not found.

            char[] arr = new char[] {'D', 'H', 'N', 'O', 'P', 'Q', 'S', 'T', 'V', 'X'};

            int ret1 = Arrays.binarySearch(arr, 'B');

            int ret2 = Arrays.binarySearch(arr, 'U');

            int ret3 = Arrays.binarySearch(arr, 'Z');

            System.out.print(ret1); System.out.print(' '); System.out.print(ret2);

            System.out.print(' '); System.out.print(ret3); System.out.print(' ');

            System.out.println();

The output is,

    -1 -9 -11

Searching a Range

The syntax to search a range of chars is:

    public static int binarySearch(char[] a, int fromIndex, int toIndex, char key)

fromIndex is the normal index at which the range starts. toIndex is the normal index just after the last element of the range. The following code segment searches the sorted array beginning from index 3 to just after index 7, which is index 8. The element for index 8 is not included in the range.

            char[] arr = new char[] {'D', 'H', 'N', 'O', 'P', 'Q', 'S', 'T', 'V', 'X'};

            int ret = Arrays.binarySearch(arr, 3, 8, 'S');

            System.out.println(ret);

The key is S, and the output is 6.

Conclusion

The Arrays syntaxes for searching an array of primitive types are:

  • public static int binarySearch(byte[] a, byte key)
  • public static int binarySearch(byte[] a, int fromIndex, int toIndex, byte key)
  • public static int binarySearch(char[] a, char key)
  • public static int binarySearch(char[] a, int fromIndex, int toIndex, char key)
  • public static int binarySearch(double[] a, double key)
  • public static int binarySearch(double[] a, int fromIndex, int toIndex, double key)
  • public static int binarySearch(float[] a, float key)
  • public static int binarySearch(float[] a, int fromIndex, int toIndex, float key)
  • public static int binarySearch(int[] a, int key)
  • public static int binarySearch(int[] a, int fromIndex, int toIndex, int key)

About the author

Chrysanthus Forcha

Discoverer of mathematics Integration from First Principles and related series. Master’s Degree in Technical Education, specializing in Electronics and Computer Software. BSc Electronics. I also have knowledge and experience at the Master’s level in Computing and Telecommunications. Out of 20,000 writers, I was the 37th best writer at devarticles.com. I have been working in these fields for more than 10 years.