Binary search algorithm

• Binary search algorithm

In computer science, a binary search or half-interval search algorithm finds the position of a specified value (the input "key") within a sorted array.
In each step, 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 or, if the input key is greater, on the sub-array to the right

http://en.wikipedia.org/wiki/Binary_search_algorithm

• Binary search algorithm

It means, that in worst case, algorithm makes 20 steps to find a value in sorted array of a million elements or to say, that it doesn't present it the array.


Algorithm

Algorithm is quite simple. It can be done either recursively or iteratively:

get the middle element;
if the middle element equals to the searched value, the algorithm stops;
otherwise, two cases are possible:
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.
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.
   
   
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);        
}


http://www.algolist.net/Algorithms/Binary_search

• İkili Arama Algoritması (Binary Search Algorithm)

http://www.bilgisayarkavramlari.com/2009/12/21/ikili-arama-algoritmasi-binary-search-algorithm/

• İkili arama algoritması

http://tr.wikipedia.org/wiki/%C4%B0kili_arama_algoritmas%C4%B1

• Binary Search - Example, Explanations, Algorithm & Code Part 2/2

http://www.youtube.com/watch?v=ZvJA-bdIvN8