Algorithm Implementation/Search/Binary search
(Redirected from Algorithm implementation/Search/Binary search)
The following Ada implementation used a generic approach to enable searches on arbitrary data.
generictypeElement_Typeisprivate;typeIndex_Typeisrange<>;typeArray_Typeisarray(Index_Typerange<>)ofElement_Type;withfunction"<" (Left :inElement_Type; Right :inElement_Type)returnBooleanis<>;procedureSearch (Elements :inArray_Type; Search :inElement_Type; Found :outBoolean; Index :outIndex_Type'Base)isLeft : Index_Type'Base := Elements'First; Right : Index_Type'Base := Elements'Last + 1;beginifSearch < Elements (Left)thenIndex := Left - 1; Found := False;elseloopdeclareCenter :constantIndex_Type := Left + (Right - Left) / 2; Candidate :constantElement_Type := Elements (Center);beginifSearch = CandidatethenIndex := Center; Found := True;exit;endif;ifRight - Left <= 1thenIndex := Center; Found := False;exit;elsifSearch < CandidatethenRight := Center;elseLeft := Center;endif;end;endloop;endif;return;endSearch;
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;
}
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;
}
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;
}
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 */
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;
}
(* 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;
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 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 */
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
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;
}
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
# 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