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