A search algorithm called binary search determines where a target value is located within a set of sorted data, for instance, in an array. The search algorithm is quick and has an O run-time complexity (log n).
Binary search compares the target value to the array's middle element; if they are not equal, the half of the array where the target cannot be is deleted, and the search is then repeated on the remaining half until it is successful. The target is not in the array if the search is successful and the remaining half is empty.
package com.BinarySearch;
public class Test {
public static int binarySearch(int[] data, int key){
int start = 0;
int end = data.length - 1;
while (start <= end) {
int mid = (start + end) / 2;
if (key == data[mid]) {
return mid;
}
if (key < data[mid]) {
end = mid - 1;
} else {
start = mid + 1;
}
}
return -1;
}
public static void main(String args[]){
int[] data= {58,120,130,140,160,800,900};
int key = 140;
System.out.println(key+" found at: "+binarySearch(data, key));
}
}
Output