Problem

Consider the provided main method which provides a sorted array of integers, and an integer value x. Write a method which performs a binary search of the array for the value x.

    public static void main(String [] args)
    {
        int [] array = {1,2,3,3,3,5,6,7};   // the array to search
        int x = 4;                          // the element we are searching for
        boolean found = false;


        // search for element x
        found = binarySearch (array, x);

        // provide some nice output
        if (found)
            System.out.println("The element " + x + " exists in the array");
        else
        System.out.println("The element " + x + " does not exists in the array");

    } // main

The method should accepts an array of integers and an integer value x. The method should perform a binary search of the array. The method should return true if the value x occurs in the array, otherwise the method should return false.

...by students

Taken from http://www.flickr.com/photos/daniello/565304023/

An image or By Students section

Solution

Create a method to search the array. The method will accept accepts an array of integers and an integer value x. The method will return true if the value x occurs in the array, otherwise the method should return false.

private static boolean binarySearch (int [] array, int x)
{
}

Declare the variables we will need. We will integers to store the upper and lower bounds of our search. We will need an integer to calculate the middle of our search bounds. We will also need a boolean to indicate whether our x value has been found.

boolean found = false;
int upperBound;
int lowerBound;
int mid;

Before trying to search the array, make sure it is properly initialized. If the array is null, we cannot search the array, so we will return false.

if (array != null)
{
}

Initialize the values of the bounds of our search.

Return true if the value x occurs in the array, otherwise return false.

return found;

Code

Solution Code

public class BinarySearchX
{

    public static void main(String [] args)
    {
        int [] array = {1,2,3,3,3,5,6,7};   // the array to search
        int x = 4;                          // the element we are searching for
        boolean found = false;


        // search for element x
        found = binarySearch (array, x);

        // provide some nice output
        if (found)
            System.out.println("The element " + x + " exists in the array");
        else
        System.out.println("The element " + x + " does not exists in the array");

    } // main

    private static boolean binarySearch (int [] array, int x)
    {
        boolean found = false;
        int upperBound;
        int lowerBound;
        int mid;

        if (array != null)
        {
            upperBound = array.length -1;
            lowerBound = 0;

            while (!found && upperBound >= lowerBound)
            {
                mid = (upperBound + lowerBound) / 2;

                if (array [mid] < x)
                    lowerBound = mid + 1;

                else if (array [mid] > x)
                    upperBound = mid - 1;

                else
                    found = true;
            } //while
        } // if

        return found;
    } // binarySearch
} // BinarySearchX