# Algorithm Implementation/Search/Binary search

The following Ada implementation used a generic approach to enable searches on arbitrary data.

generic
type Element_Type is private;
type Index_Type is range <>;
type Array_Type is
array (Index_Type range <>) of Element_Type;
with function "<"
(Left  : in Element_Type;
Right : in Element_Type)
return  Boolean
is <>;
procedure Search
(Elements : in Array_Type;
Search   : in Element_Type;
Found    : out Boolean;
Index    : out Index_Type'Base)
is
Left  : Index_Type'Base := Elements'First;
Right : Index_Type'Base := Elements'Last + 1;
begin
if Search < Elements (Left) then
Index := Left - 1;
Found := False;
else
loop
declare
Center    : constant Index_Type   :=
Left + (Right - Left) / 2;
Candidate : constant Element_Type :=
Elements (Center);
begin
if Search = Candidate then
Index := Center;
Found := True;
exit;
end if;

if Right - Left <= 1 then
Index := Center;
Found := False;
exit;
elsif Search < Candidate then
Right := Center;
else
Left := Center;
end if;
end;
end loop;
end if;
return;
end Search;

## C

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

## C++

The following is a recursive binary search in C++, designed to take advantage of the C++ STL vectors.

//! \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);
}

A small test suite for the above binary search implementation:

#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;
}

## C++ (generic w/ templates)

Here is a more generic iterative binary search using the concept of iterators:

//! \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;
}

## C++ (common Algorithm)

A common binary search Algorithm with its pseudocode:

//! \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;
}

/*
BEGIN BinarySearch(data, size, data2Search)
SET low to 0, high to size-1
WHILE low is smaller than or equal to high
SET midpoint to (low + high) / 2
IF data2Search is equal to data[midpoint] THEN
return midpoint
ELSEIF data2Search is smaller than data[midpoint] THEN
SET high to midpoint - 1
ELSE
SET low to midpoint + 1
ENDIF
ENDWHILE
END */

## C# (common Algorithm)

A common binary search Algorithm:

/**
* Binary search finds item in sorted array.
* And returns index (zero based) of item
* 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;
}

return -1;
}

## Delphi

(* 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;

## Java

Binary Search implementation in Java. The algorithm is implemented recursively.

/* 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 = (left + right) / 2;

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

Joshua Bloch wrote the binary search in "java.util.Arrays", so perhaps he knows a thing or two about binary searching in Java.[1]

Test class for a BinarySearch class. Note: Array must be sorted before binary search.

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

## JavaScript

JavaScript binary search algorithm with loop:

/**
* Find an index of the element in the array haystack with value needle
* @param {number[]}      haystack array of number elements
* @param {number} needle needle to find in the haystack
* @returns {null|number} return index of the element or null if not found
*/
function binarySearch(haystack, needle) {
var low = 0
var high = haystack.length - 1
while (low <= high) {
// average between high and low
var average = (high - low) / 2
// round average to integer e.g. 7.5 to 7 so we can use it as array index
average = Math.floor(average)
// index of middle element
var middle = low + average
var element = haystack[middle]
if (needle == element) {
return middle
} else {
if (needle > element) {
low = middle + 1
} else {
high = middle - 1
}
}
}
return null
}

var haystack = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
var index = binarySearch(haystack, 14)
console.log(index)
//=> 14

var indexNotFound = binarySearch(haystack, 16)
console.log(indexNotFound)
//=> null

JavaScript binary search algorithm implemented on all Array objects using prototype chaining.

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

Example:

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 */

## Phix

Note this is available as a builtin

global function binary_search(object needle, sequence haystack)
integer lo = 1,
hi = length(haystack),
mid = lo,
c = 0

while lo<=hi do
mid = floor((lo+hi)/2)
c = compare(needle, haystack[mid])
if c<0 then
hi = mid-1
elsif c>0 then
lo = mid+1
else
return mid  -- found!
end if
end while
mid += c>0
return -mid         -- where it would go, if inserted now
end function

## PHP

Working PHP binary search code. Note that this code is extremely inefficient because of the use of array_slice.

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

Here is a better version from the PHP documentation

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

## Python

Working python binary search code.

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)

That code isn't exactly idiomatic. It's a class, but it has no state. Additionally, it unnecessarily consumes stack space by recursing. Here is another version: (Not binary search actually but binary + linear)

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

## Ruby

# 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

Example:

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