Jump to content

Algorithm Implementation/Search/Binary search

From Wikibooks, open books for an open world

Wikipedia has related information at Binary search algorithm

Ada

[edit | edit source]

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;

C

[edit | edit source]
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++

[edit | edit source]

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{{typo help inline|reason=similar to coassert|date=July 2023}}>
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)

[edit | edit source]

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)

[edit | edit source]

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

C# (common Algorithm)

[edit | edit source]

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

[edit | edit source]
(* 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

[edit | edit source]

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

[edit | edit source]

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

[edit | edit source]

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

[edit | edit source]

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

[edit | edit source]

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

[edit | edit source]
# 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

Further reading

[edit | edit source]
  1. ↑ Joshua Bloch. "Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken" 2006.


Retrieved from "https://en.wikibooks.org/w/index.php?title=Algorithm_Implementation/Search/Binary_search&oldid=4308128"