View source for Algorithm implementation/Search/Binary search

{{wikipedia|Binary search algorithm}}

__TOC__

== [[Ada Programming|Ada]] ==

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

   {{Ada/Sourceforge|Algorithms/binary_search.adb}}

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

== [[wikipedia:Java programming language|Java]] ==

Binary Search implementation in Java. The algorithm is recursive implemented.
<source lang="java">
/* 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;
		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;
		}		
	}
}

</source>
Test class for a BinarySearch class.
Note: Array must be sorted before binary search.
<source lang="java">
/* 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));
	}
}
</source>

== [[wikipedia:Java programming language|Java]] using java.util ==

In Java '''java.util.Arrays''' have an overloaded version of binarySearch for all types of '''Object'''s and variables<br />
Here's an example of using it with an int[]:
<source lang="java">
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)");
	}
}
</source>

You can also use it with '''Object'''s. 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.
<source lang="java">
/** 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;
}
</source>

If you want to use this class in Arrays.sort or Arrays.binarySearch, you need to create another class, which can compare two IntHolders:
<source lang="java">
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();
	}
}
</source>

Now finally here's the example:
<source lang="java">
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));
</source>

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'''.

== [[wikipedia:Python programming language|Python]] ==

If 'search' is in 'seq' then its index is returned. Otherwise <math>-ind - 1</math> is returned, where ind is the index where 'search' should be inserted in 'seq'

 '''def''' binsearch(seq, search):    
    right = len(seq)
    left = 0
    previous_center = -1
    '''if''' search < seq[0]:
        '''return''' -1
    '''while''' 1:
        center = (left + right) / 2
        candidate = seq[center]
        '''if''' search == candidate:
            return center
        '''if''' center == previous_center:
            return - 2 - center
        '''elif''' search < candidate:
            right = center
        '''else''':
            left = center
        previous_center = center


Working python binary search code.
<pre>
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)
                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)
</pre>

That code isn't exactly idiomatic.  It's a class, but it has no state.  Additionally, it unnecessarily consumes stack space by recursing, and throws an index error if arr[-1] < searchValue.
Here is another version:
(Not binary search actually but binary + linear)
<pre>
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
</pre>

== [[w:Ruby (programming language)|Ruby]] ==

  ''# array needs to be sorted beforehand''
  '''def''' binary_search(array, val, left = 0, right = '''nil''')
    right = array.size '''unless''' right;
    mid = (left + right) / 2;
  
    '''return''' '''nil''' '''if''' left > right
  
    '''if''' val == array[mid]
      '''return''' mid
    '''elsif''' val > array[mid]
      binary_search(array, val, mid + 1, right)
    '''else'''
      binary_search(array, val, left, mid - 1)
    '''end'''
  '''end'''

Example:

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

== [[w: C++ (programming language)|C++]] ==

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

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

A small test suite for the above binary search implementation:

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

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

int main(int argc, char* argv[])
{
    // 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;
}
</pre>

==[[w: C++ (programming language)|C++ (generic w/ templates)]]==

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

<pre>
//! \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 halfing the search space until we reach the end of the vector
    Iterator Middle;
    Iterator NotFound = end;

    while(begin < end)
    {
        // Find the median value between the iterators
        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;
}
</pre>

==[[w: C++ (programming language) | C++ (common Algorithm)]]==

A common binary search Algorithm with its pseudocode:

<pre>
//! \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) / 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
	RETURN -1 // Target not found
END */
</pre>


==[[wikipedia:Delphi programming language|Delphi]]==

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

[[Category:Algorithms|Binary search]]