[algorithm]Binary search algorithm

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:

/**

 * 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);
}

non-recursive:

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;

}