Algorithm implementation/Search/Binary search
Jump to navigation
Jump to search
The following Ada implementation used a generic approach to enable searches on arbitrary data.
Template:Ada/Sourceforge
Template:Ada/kw Template:Ada/kw Element_Type Template:Ada/kw Template:Ada/kw; Template:Ada/kw Index_Type Template:Ada/kw Template:Ada/kw Template:Ada/delimiter 2; Template:Ada/kw Array_Type Template:Ada/kw Template:Ada/kw (Index_Type Template:Ada/kw Template:Ada/delimiter 2) Template:Ada/kw Element_Type; Template:Ada/kw Template:Ada/kw "<" (Left : Template:Ada/kw Element_Type; Right : Template:Ada/kw Element_Type) Template:Ada/kw Boolean Template:Ada/kw Template:Ada/delimiter 2; Template:Ada/kw Search (Elements : Template:Ada/kw Array_Type; Search : Template:Ada/kw Element_Type; Found : Template:Ada/kw Boolean; Index : Template:Ada/kw Index_Type'Template:Ada/attribute) Template:Ada/kw Left : Index_Type'Template:Ada/attribute := Elements'Template:Ada/attribute; Right : Index_Type'Template:Ada/attribute := Elements'Template:Ada/attribute + 1; Template:Ada/kw Template:Ada/kw Search < Elements (Left) Template:Ada/kw Index := Left - 1; Found := False; Template:Ada/kw Template:Ada/kw Template:Ada/kw Center : Template:Ada/kw Index_Type := Left + (Right - Left) / 2; Candidate : Template:Ada/kw Element_Type := Elements (Center); Template:Ada/kw Template:Ada/kw Search = Candidate Template:Ada/kw Index := Center; Found := True; Template:Ada/kw; Template:Ada/kw Template:Ada/kw; Template:Ada/kw Right - Left <= 1 Template:Ada/kw Index := Center; Found := False; Template:Ada/kw; Template:Ada/kw Search < Candidate Template:Ada/kw Right := Center; Template:Ada/kw Left := Center; Template:Ada/kw Template:Ada/kw; Template:Ada/kw; Template:Ada/kw Template:Ada/kw; Template:Ada/kw Template:Ada/kw; Template:Ada/kw; Template:Ada/kw Search;
Binary Search implementation in Java. The algorithm is recursive implemented.
/* 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) / 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;
}
}
}
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.
If 'search' is in 'seq' then its index is returned. Otherwise 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
# array needs to be sorted beforehand
def binary_search(array, val, left = 0, right = nil)
right = array.size unless right;
mid = (left + right) / 2;
return nil if left > right
if val == array[mid]
return mid
elsif val > array[mid]
binary_search(array, val, mid + 1, right)
else
binary_search(array, val, left, mid - 1)
end
end
Example:
a = [1, 3, 6, 8, 12, 14, 15, 20, 142]
puts [12, 1, 20, 142, 5].each { |i| binary_search(a, i) }.join(', ')
# => 4 0 7 8 nil
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;
}
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;
}
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 */
(* 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;