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

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

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

## Java using java.util

In Java java.util.Arrays have an overloaded version of binarySearch for all types of Objects and variables
Here's an example of using it with an int[]:

```import java.util.Arrays;
public class BinarySearchTest {
public static void main(String[] args) {
int[] arr = {1, 5, 2, 7, 9, 5};

// Precondition to the Arrays.binarySearch
Arrays.sort(arr);

// Search an element
int index = Arrays.binarySearch(arr, 3);

if (index >= 0)
System.out.println("Data found at " + index + " (0-based)");
else // index < 0
System.out.println("Data not found. It should be inserted before the " + (-index - 1) + ". element (0-based)");
}
}
```

You can also use it with Objects. First of all you need an object. In this case it's the IntHolder, which holds an integer for the reason of simplicity. It has a Constructor, and a getter function to handle that integer. Discard Comparable and compareTo for this time.

```/** A class that holds an integer*/
class IntHolder implements Comparable<IntHolder> {
public IntHolder(int num) {
this.num = num;
}
// implenets the Interface Comparable
public int compareTo(IntHolder o) {
return this.num - o.num;
}
public int getNum() {
return num;
}
private int num;
}
```

If you want to use this class in Arrays.sort or Arrays.binarySearch, you need to create another class, which can compare two IntHolders:

```import java.util.Comparator;
/** A class that can compare two IntHolders*/
class IntHolderComparator implements Comparator<IntHolder> {
/** returns < 0 if o1 < o2; > 0 if o1 > o2; and 0 if o1 == o2 */
public int compare(IntHolder o1, IntHolder o2) {
return o1.getNum() - o2.getNum();
}
}
```

Now finally here's the example:

```IntHolder[] oArr = {
new IntHolder(1), new IntHolder(5),
new IntHolder(2), new IntHolder(7),
new IntHolder(9), new IntHolder(5)
};

// Precondition to the Arrays.binarySearch
IntHolderComparator comp = new IntHolderComparator();
Arrays.sort(oArr, comp);

// if the class don't have a public int compareTo(Object) method, use Comparator
int oIndexC = Arrays.binarySearch(oArr, new IntHolder(2), new IntHolderComparator());

// else use it as any builtin primitive type
int oIndex = Arrays.binarySearch(oArr, new IntHolder(2));
```

As you can see, one can use Arrays.binarySearch without a Comparator. This can be achieved if your class implements the Comparable interface shown above. This also applies to Arrays.sort.

## 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
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:

```a = [1, 3, 6, 8, 12, 14, 15, 20, 142].sort

puts [12, 1, 20, 142, 5].map { |i|
a.binary_search(i)
}.join(', ')
# => 4, 0, 7, 8, nil
```

## 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, unsigned start, unsigned 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.
unsigned 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
Iterator NotFound = end;

while(begin < end)
{
// Find the median value between the iterators
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 value, int& position)
{
int low = 0, high = Size - 1, midpoint = 0;
while (low <= high)
{
midpoint = low + (high - low)/2;
if (value == array[midpoint])
{
position = midpoint;
return true;
}
else if (value < array[midpoint])
high = midpoint - 1;
else
low = midpoint + 1;
}
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
* 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;
}

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