Binary Search In Java
Chapter:
Miscellaneous
Last Updated:
19-07-2016 03:15:40 UTC
Program:
/* ............... START ............... */
import java.util.Scanner;
public class JavaBinarySearch {
public static void main(String args[]) {
int c, first, last, middle, n, search, array[];
Scanner in = new Scanner(System.in);
System.out.println("Enter number of elements");
n = in.nextInt();
array = new int[n];
System.out.println("Enter " + n + " integers");
for (c = 0; c < n; c++)
array[c] = in.nextInt();
System.out.println("Enter value to find");
search = in.nextInt();
first = 0;
last = n - 1;
middle = (first + last) / 2;
while (first <= last) {
if (array[middle] < search)
first = middle + 1;
else if (array[middle] == search) {
System.out.println(search + " found at location " + (middle + 1) + ".");
break;
} else
last = middle - 1;
middle = (first + last) / 2;
}
if (first > last)
System.out.println(search + " is not present in the list.\n");
}
}
/* ............... END ............... */
Output
Enter number of elements
5
Enter 5 integers
10
46
34
24
2
Enter value to find
34
34 found at location 3.
Notes:
-
A binary search or half-interval search algorithm finds the position of a specified value (the input "key") within a sorted array.
- The algorithm compares the input key value with the key value of the middle element of the array. If the keys match, then a matching element has been found so its index, or position, is returned. Otherwise, if the sought key is less than the middle element's key, then the algorithm repeats its action on the sub-array to the left of the middle element.
- Every iteration eliminates half of the remaining possibilities. This makes binary searches very efficient - even for large collections.
- Worst case performance: O(log n).
- Best case performance: O(1).
Tags
Binary Search, Java