Algorithm Implementation/Search/Binary search

Ada

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

File: Algorithms/binary_search.adb (view, plain text, download page, browse all)

  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.

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

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
        RETURN -1 // Target not found
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;
    }
 
    // item was not found
    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;