Problem

Consider the 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:

1. accept an array of integers and an integer value
2. perform a binary search of the array
3. return true if the value x occurs in the array, otherwise return false

...by students

During the early years in computer science, we have to complete assignment after assignment for our many computer science courses. Personally, I found myself very stressed out and rushed during this time. Sometimes I would find myself jumping back and forth between the several programs I had to write at the time. Whenever I had to switch from one program to the other, I would spend a lot of time trying to find my place and figure out what I was doing. That's when I decided that comments were my friend. Comments made it easier to figure out what I was doing and what I should do next. Even though it seemed like it would take more time to write the comments, I saved lots of time in the long run. The moral of the story is, not only does it make it easier to do your assignment, but you don't lose marks for not including comments in your code.

Solution

Create a method to search the array. This method will accept an array of integers and an integer value x. The method will then 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 need:

• integers to store the upper and lower bounds of our search
• integer to calculate the middle of our search bounds
• 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. On our first iteration, we will consider the entire array. Set the lower bound to the first element of the array and the upper bound to the last element of the array.

 upperBound = array.length -1;
lowerBound = 0; 

Begin searching the array. We will continue to search the array until either we find the value we are looking for, or until we exhaust our search.

 while (!found && upperBound >= lowerBound)
{
} 

Calculate the index of the element in the middle of our upper and lower bounds. To find the middle element, add our upper and lower bounds and divide the result by two.

 mid = (upperBound + lowerBound) / 2; 

Compare the value of the middle element with the value of x. If the values are equal, we found the element we are looking for. We complete our search by indicating that the value of x has been found.

If the value of x is greater than that of the middle element, we can assume that the value of x is should be between the middle element and the upper bound. Therefore, we adjust our lower bound to consider only elements between the middle and the upper bound for the next iteration of our search.

If the value of x is less than the value of the middle element, we can assume that the value of x should be between the middle element and the lower bounds. Therefore, we adjust our upper bound to consider only elements between the middle and the lower bound for the next iteration of our search.

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

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

else
    found = true; 

Return true if the value x was found 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

    // searches through an array of sorted integers, returning true if x is found in the array
    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;    // mid = half of the section we are looking at

                if (array [mid] < x)         // if the element is greater than mid, change lowerBound
                    lowerBound = mid + 1;

                else if (array [mid] > x)    // if the element is lower than mid, change upperBound
                    upperBound = mid - 1;

                else                        // else the element is equal to mid, therefore it is found
                    found = true;
            } //while
        } // if

        return found;
    } // binarySearch
} // BinarySearchX