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
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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
import javax.swing.*; public class BinarySearch { public static void main(String[] args) { int array[] = new int[11]; array[0] = 10; array[1] = 20; array[2] = 30; array[3] = 40; array[4] = 50; array[5] = 60; array[6] = 70; array[7] = 80; array[8] = 90; array[9] = 100; array[10] = 110; int size = array.length; int low = 0; int mid = low+size/2; int num=0; System.out.println("The current array contains following data: "); for(int i = 0 ; i<=10 ; i++) { System.out.print(array[i]+"\t"); } System.out.println(); String input_box = JOptionPane.showInputDialog("Enter the element to be searched: "); try //Putting the main code in the try block. { num = Integer.parseInt(input_box); if(num>array[size-1] || num < array[0]) //Main if { System.out.println("Number doesn't exist."); } else{ while(array[(low+size)/2]!= num){ if(num>array[(low+size)/2]) { System.out.println("Setting low to "+mid); low = mid; mid=(mid+size)/2; }//End if else{ System.out.println("Setting size to "+mid); size = mid; mid=mid/2; } }//Close while loop System.out.println("The number is at position: "+(low+size)/2); }//End main if }//End try catch(Exception e)//Catching exception { JOptionPane.showMessageDialog(null, "Error:\nYou need to enter a number,not string", "Invalid Number!", JOptionPane.WARNING_MESSAGE); } } } |
Tested in Eclipse.
Vlad
Latest posts by Vlad (see all)
- Code jam “Tic-Tac-Toe-Tomek” solution in java - April 19, 2013
- Code jam “Minimum Scalar product” solution in java - March 18, 2013
- Code jam Store Credit solution in java - March 10, 2013
