Find Element x Using Binary Search
Back to the Program-A-Day homepage
ProblemConsider 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:
|
...by studentsDuring 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. | |
|---|---|---|
SolutionCreate 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:
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 | ||
