Algorithm Implementation/Search/Binary search

int SortedArray[max] = {....}

int BinarySearch (int key)
{
    int start = 0;
    int end = max - 1;
    int mid;
    while (start <= end)
    {
        mid = (start + end) / 2;
        if (key == a[mid])
            return mid;
        else if (key < a[mid])
            end = mid - 1;
        else start = mid + 1;
    }
    return -1;
}

//! \brief A recursive binary search using STL vectors
//! \param vec The vector whose elements are to be searched
//! \param start The index of the first element in the vector
//! \param end The index of the last element in the vector
//! \param key The value being searched for
//! \return The index into the vector where the value is located,
//! or -1 if the value could not be found.
template<typename T>
int binary_search(const std::vector<T>& vec, int start, int end, const T& key)
{
    // Termination condition: start index greater than end index
    if(start > end)
    {
        return -1;
    }

    // Find the middle element of the vector and use that for splitting
    // the array into two pieces.
    const int middle = start + ((end - start) / 2);

    if(vec[middle] == key)
    {
        return middle;
    }
    else if(vec[middle] > key)
    {
        return binary_search(vec, start, middle - 1, key);
    }

    return binary_search(vec, middle + 1, end, key);
}

#include <vector>
#include <cassert>
using namespace std;

//! \brief A helper function for the binary search
template<typename T>
int search(const vector<T>& vec, const T& key)
{
    return binary_search(vec, 0, vec.size()-1, key);
}

int main()
{
    // Create and output the unsorted vector
    vector<int> vec;
    vec.push_back(1);
    vec.push_back(5);
    vec.push_back(13);
    vec.push_back(18);
    vec.push_back(21);
    vec.push_back(43);
    vec.push_back(92);

    // Use our binary search algorithm to find an element
    int search_vals[] = {1, 5, 19, 21, 92, 43, 103};
    int expected_vals[] = {0, 1, -1, 4, 6, 5, -1};

    for(unsigned i = 0; i < 7; i++)
    {
        assert(expected_vals[i] == search(vec, search_vals[i]));
    }

    return 0;
}

//! \brief A more generic binary search using C++ templates and iterators
//! \param begin Iterator pointing to the first element
//! \param end Iterator pointing to one past the last element
//! \param key The value to be searched for
//! \return An iterator pointing to the location of the value in the given
//! vector, or one past the end if the value was not found.
template<typename Iterator, typename T>
Iterator binary_search(Iterator& begin, Iterator& end, const T& key)
{
    // Keep halving the search space until we reach the end of the vector
    const Iterator NotFound = end;

    while(begin < end)
    {
        // Find the median value between the iterators
        const Iterator Middle = begin + (std::distance(begin, end) / 2);

        // Re-adjust the iterators based on the median value
        if(*Middle == key)
        {
            return Middle;
        }
        else if(*Middle > key)
        {
            end = Middle;
        }
        else
        {
            begin = Middle + 1;
        }
    }

    return NotFound;
}

//! \A common binary search Algorithm with its pseudocode

    bool binarySearch(int array[], int Size, int key, int& location)
    {
	int low = 0, high = Size - 1, midpoint = 0;
	while (low <= high)
	{
		midpoint = low + (high - low)/2;
		if (key== array[midpoint])
		{
			location = midpoint;
			return true;
		}
		else if (key< array[midpoint])
			high = midpoint - 1;
		else
			low = midpoint + 1; //when key is > array[midpoint]
	}
	return false;
    }

/**
 * Binary search finds item in sorted array.
 * And returns index (zero based) of item
 * If item is not found returns -1
 * Based on C++ example at
 * http://en.wikibooks.org/wiki/Algorithm_implementation/Search/Binary_search#C.2B.2B_.28common_Algorithm.29
 **/
static int BinarySearch(int[] array, int value)
{       
    int low = 0, high = array.Length - 1, midpoint = 0;
    
    while (low <= high)
    {
        midpoint = low + (high - low)/2;      

        // check to see if value is equal to item in array
        if (value == array[midpoint])
        {                    
            return midpoint;
        }
        else if (value < array[midpoint])
            high = midpoint - 1;
        else
            low = midpoint + 1;
    }

    // item was not found
    return -1;
}

(* Returns index of requested value in an integer array that has been sorted
in ascending order -- otherwise returns -1 if requested value does not exist. *)

function BinarySearch(const DataSortedAscending: array of Integer;
 const ElementValueWanted: Integer): Integer;
var
    MinIndex, MaxIndex: Integer;
    { When optimizing remove these variables: }
    MedianIndex, MedianValue: Integer;
begin
    MinIndex := Low(DataSortedAscending);
    MaxIndex := High(DataSortedAscending);
    while MinIndex <= MaxIndex do begin
        MedianIndex := (MinIndex + MaxIndex) div 2; (* If you're going to change
         the data type here e.g. Integer to SmallInt consider the possibility of
         an overflow. All it needs to go bad is MinIndex=(High(MinIndex) div 2),
         MaxIndex = Succ(MinIndex). *)
        MedianValue := DataSortedAscending[MedianIndex];
        if ElementValueWanted < MedianValue then
            MaxIndex := Pred(MedianIndex)
        else if ElementValueWanted = MedianValue then begin
            Result := MedianIndex;
            Exit; (* Successful exit. *)
        end else
            MinIndex := Succ(MedianIndex);
    end;
    Result := -1; (* We couldn't find it. *)
end;

/* BinarySearch.java */
public class BinarySearch {
	public static final int NOT_FOUND = -1;
	
	public static int search(int[] arr, int searchValue) {
		int left = 0;
		int right = arr.length - 1;
		return binarySearch(arr, searchValue, left, right);
	}
		
	private static int binarySearch(int[] arr, int searchValue, int left, int right) {
		if (right < left) {
			return NOT_FOUND;
		}
		/* 
		int mid = mid = (left + right) / 2;
		There is a bug in the above line;
		Joshua Bloch suggests the following replacement:
		*/
		int mid = (left + right) >>> 1;
		if (searchValue > arr[mid]) {
			return binarySearch(arr, searchValue, mid + 1, right);
		} else if (searchValue < arr[mid]) {
			return binarySearch(arr, searchValue, left, mid - 1);
		} else {
			return mid;
		}		
	}
}

/* BinarySearchTest.java */
import java.util.Arrays;

public class BinarySearchTest {

	public static void main(String[] args) {
		int[] arr = {1, 5, 2, 7, 9, 5};
		Arrays.sort(arr);
		System.out.println(BinarySearch.search(arr, 2));
	}
}

Array.prototype.binary_search = function(val, left, right) {
  if (typeof left === 'undefined') left = 0;
  if (typeof right === 'undefined') right = this.length - 1;
  if (left > right) return null;

  var mid = (left + right) >> 1; /* see Joshua Bloch's blog post */
                                 /* referenced in Further Reading */
                                 /* section at bottom of page */
  if (val == this[mid]) {
    return mid;
  } else if (val > this[mid]) {
    return this.binary_search(val, mid + 1, right);
  } else {
    return this.binary_search(val, left, mid - 1);
  }
}

var a = [3, 142, 1, 8, 14, 12, 6, 20, 15].sort(function(a, b){return a-b});
console.log(a.join(", "));
/* => 1, 3, 6, 8, 12, 14, 15, 20, 142 */
var targets = [12, 1, 20, 142, 5];
var result = [];
for (var i=0; i<targets.length; i++) {
  var found_at_index = a.binary_search(targets[i]);
  if (typeof found_at_index == 'number' && found_at_index >= 0) {
    result.push(found_at_index);
  } else {
    result.push("null");
  }
}
console.log(result.join(", "));
/* => 4, 0, 7, 8, null */

function binary_search($a, $k){

    //find the middle
    $middle = round(count($a)/2, 0)-1;

    //if the middle is the key we search...
    if($k == $a[$middle]){
        echo $a[$middle]." found";
        return true;
    }
    //if the array lasts just one key while the middle isn't the key we search
    elseif(count($a)==1){
        echo $k." not found";
        return false;
    }
    //if the key we search is lower than the middle
    elseif($k < $a[$middle]) {
        //make an array of the left half and search in this array
        return binary_search(array_slice($a, 0, $middle), $k);
    }
    //if the key we search is higher than the middle
    elseif($k > $a[$middle-1]) {
        //make an array of the right half and search in this array
        return binary_search(array_slice($a, $middle+1), $k);
    }     
}

function fast_in_array($elem, $array){
   $top = sizeof($array) -1;
   $bot = 0;

   while($top >= $bot)
   {
      $p = floor(($top + $bot) / 2);
      if ($array[$p] < $elem) $bot = $p + 1;
      elseif ($array[$p] > $elem) $top = $p - 1;
      else return TRUE;
   }
    
   return FALSE;
}

class BinarySearch:
        NOT_FOUND = -1

        def binarySearch(self, arr, searchValue, left, right):
                if right < left:
                        return self.NOT_FOUND

                mid = (left + right) / 2 
                if searchValue > arr[mid]:
                        return self.binarySearch(arr, searchValue, mid + 1, right)
                elif searchValue < arr[mid]:
                        return self.binarySearch(arr, searchValue, left, mid - 1)
                else:
                        return mid

        def search(self, arr, searchValue):
                left = 0
                right = len(arr) - 1
                return self.binarySearch(arr, searchValue, left, right)

if __name__ == '__main__':
        bs = BinarySearch()
        a = [1, 2, 3, 5, 9, 11, 15, 66]
        print bs.search(a, 5)

NOT_FOUND = -1

def bsearch(l, value):
    lo, hi = 0, len(l)-1
    while lo <= hi:
        mid = (lo + hi) / 2  #replace with "mid = (lo + hi) // 2" in python3
        if l[mid] < value:
            lo = mid + 1
        elif value < l[mid]:
            hi = mid - 1
        else:
            return mid
    return NOT_FOUND

if __name__ == '__main__':
    l = range(50)
    for elt in l:
        assert bsearch(l, elt) == elt
    assert bsearch(l, -60) == NOT_FOUND
    assert bsearch(l, 60) == NOT_FOUND
    assert bsearch([1, 3], 2) == NOT_FOUND

# array needs to be sorted beforehand
class Array
  def binary_search(val, left = 0, right = nil)
    right = self.size - 1 unless right
    mid = (left + right) / 2

    return nil if left > right

    if val == self[mid]
      return mid
    elsif val > self[mid]
      binary_search(val, mid + 1, right)
    else
      binary_search(val, left, mid - 1)
    end
  end
end

irb(main):018:0> a = [1, 3, 6, 8, 12, 14, 15, 20, 142].sort
=> [1, 3, 6, 8, 12, 14, 15, 20, 142]
irb(main):019:0> puts [12, 1, 20, 142, 5].map { |i|
irb(main):020:1*   a.binary_search(i)
irb(main):021:1> }.join(', ')
4, 0, 7, 8,
=> nil