Binary search algorithm time complexity is O(log2(n)), and this algorithm requires that source array is sorted in order to work correct.
Algorithm is quite simple. It can be done either recursively or iteratively:
1.get the middle element;
2.if the middle element equals to the searched value, the algorithm stops;
3.otherwise, two cases are possible:
(1)searched value is less, than the middle element. In this case, go to the step 1 for the part of the array, before middle element.
(2)searched value is greater, than the middle element. In this case, go to the step 1 for the part of the array, after middle element.
recursive:
[code lang=”java”]
/**
* searches for a value in sorted array
*
* @param array
* array to search in
* @param value
* searched value
* @param left
* index of left boundary
* @param right
* index of right boundary
* @return position of searched value, if it presents in the array or -1, if
* it is absent
*/
int binarySearch(int[] array, int value, int left, int right) {
if (left > right)
return -1;
int middle = (left + right) / 2;
if (array[middle] == value)
return middle;
else if (array[middle] > value)
return binarySearch(array, value, left, middle – 1);
else
return binarySearch(array, value, middle + 1, right);
}
[/code]
non-recursive:
[code lang=”java”]
int binarySearch2(int[] array, int value, int left, int right){
while (left <= right){
int middle = (left + right) / 2;
if (array[middle] == value){
return middle;
} else if (array[middle] > value) {
right = middle – 1;
} else if (array[middle] < value) {
left = middle + 1;
}
}
return -1;
}
[/code]