Algorithm Implementation/Search/Binary search

Wikipedia has related information at Binary search algorithm

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;

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

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

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

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