Java program to perform binary search

This is a program which will do a binary search for you. First, lets learn what binary search really is.
Binary search at wikipedia:
In computer science, a binary search or half-interval search algorithm locates the position of an item in a sorted array. Binary search works by comparing an input value to the middle element of the array. The comparison determines whether the element equals the input, less than the input or greater. When the element being compared to equals the input the search stops and typically returns the position of the element. If the element is not equal to the input then a comparison is made to determine whether the input is less than or greater than the element. Depending on which it is the algorithm then starts over but only searching the top or bottom subset of the array’s elements. If the input is not located within the array the algorithm will usually output a unique value indicating this. Binary search algorithms typically halve the number of items to check with each successive iteration, thus locating the given item (or determining its absence) in logarithmic time.

Source: http://en.wikipedia.org/wiki/Binary_search_algorithm

Example:
Consider an sorted array containing 5,15,25,30,35,40
Sorted array for binary search
Suppose we want to search for the number 30 in the given array. The algorithm performs the search in the following steps.
Step 1:
Compare the number to be searched with the middle element i.e 20 in this case. So the algorithm compares the number 30 with 20.

Step 2:
If the number to be searched is greater than the middle number, search operation is performed on the second part of the array. Else, on the first part of the array.

The procedure continues till array[mid] is the number requested by the user.

Program:

Tested in Eclipse.

The following two tabs change content below.

4 thoughts on “Java program to perform binary search

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">