Algorithm Implementation/Search/Binary search
From Wikibooks, the open-content textbooks collection
< Algorithm Implementation | Search(Redirected from Algorithm implementation/Search/Binary search)
Contents |
[edit] Ada
The following Ada implementation used a generic approach to enable searches on arbitrary data.
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;
[edit] 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; 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) >>> 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; } } }
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)); } }
[edit] 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.
[edit] 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, count($a)), $k); } }
[edit] Python
If 'search' is in 'seq' then its index is returned. Otherwise − ind − 1 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.
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)
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)
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
[edit] Ruby
# array needs to be sorted beforehand
class Array
def binary_search(val, left = 0, right = nil)
right = self.size 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
[edit] 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 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);
}
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
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;
}
[edit] 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 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;
}
[edit] 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) / 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 */
[edit] 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) / 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;
}
[edit] 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;
