Binary search: Difference between revisions
(→{{header|PHP}}: guessing numbers, should be searching an array) |
(→Iterative: fix) |
||
Line 359: | Line 359: | ||
(do () ((< high low) nil) |
(do () ((< high low) nil) |
||
(let ((middle (floor (+ low high) 2))) |
(let ((middle (floor (/ (+ low high) 2)))) |
||
(cond ((> (aref array middle) value) |
(cond ((> (aref array middle) value) |
Revision as of 13:09, 3 November 2008
You are encouraged to solve this task according to the task description, using any language you may know.
A binary search divides a range of values into halves, and continues to narrow down the field of search until the unknown value is found. It is the classic example of a "divide and conquer" algorithm.
As an analogy, consider the children's game "guess a number." The host has a secret number, and will only tell the player if their guessed number is higher than, lower than, or equal to the secret number. The player then uses this information to guess a new number.
As the player, one normally would start by choosing the range's midpoint as the guess, and then asking whether the guess was higher, lower, or equal to the secret number. If the guess was too high, one would select the point exactly between the range midpoint and the beginning of the range. If the original guess was too low, one would ask about the point exactly between the range midpoint and the end of the range. This process repeats until one has reached the secret number.
Given the starting point of a range, the ending point of a range, and the "secret value", implement a binary search through a sorted integer array for a certain number. Implementations can be recursive or iterative (both if you can). Print out whether or not the number was in the array afterwards. If it was, print the index also. The algorithms are as such (from the wikipedia):
Recursive Pseudocode:
BinarySearch(A[0..N-1], value, low, high) { if (high < low) return not_found mid = (low + high) / 2 if (A[mid] > value) return BinarySearch(A, value, low, mid-1) else if (A[mid] < value) return BinarySearch(A, value, mid+1, high) else return mid }
Iterative Pseudocode:
BinarySearch(A[0..N-1], value) { low = 0 high = N - 1 while (low <= high) { mid = (low + high) / 2 if (A[mid] > value) high = mid - 1 else if (A[mid] < value) low = mid + 1 else return mid } return not_found }
Ada
Both solutions are generic. The element can be of any comparable type (such that the operation < is visible in the instantiation scope of the function Search). Note that the completion condition is different from one given in the pseudocode example above. The example assumes that the array index type does not overflow when mid is incremented or decremented beyond the corresponding array bound. This is a wrong assumption for Ada, where array bounds can start or end at the very first or last value of the index type. To deal with this, the exit condition is rather directly expressed as crossing the corresponding array bound by the coming interval middle.
Recursive
<Ada> with Ada.Text_IO; use Ada.Text_IO;
procedure Test_Recursive_Binary_Search is
Not_Found : exception; generic type Index is range <>; type Element is private; type Array_Of_Elements is array (Index range <>) of Element; with function "<" (L, R : Element) return Boolean is <>; function Search (Container : Array_Of_Elements; Value : Element) return Index;
function Search (Container : Array_Of_Elements; Value : Element) return Index is Mid : Index; begin if Container'Length > 0 then Mid := (Container'First + Container'Last) / 2; if Value < Container (Mid) then if Container'First /= Mid then return Search (Container (Container'First..Mid - 1), Value); end if; elsif Container (Mid) < Value then if Container'Last /= Mid then return Search (Container (Mid + 1..Container'Last), Value); end if; else return Mid; end if; end if; raise Not_Found; end Search;
type Integer_Array is array (Positive range <>) of Integer; function Find is new Search (Positive, Integer, Integer_Array); procedure Test (X : Integer_Array; E : Integer) is begin New_Line; for I in X'Range loop Put (Integer'Image (X (I))); end loop; Put (" contains" & Integer'Image (E) & " at" & Integer'Image (Find (X, E))); exception when Not_Found => Put (" does not contain" & Integer'Image (E)); end Test;
begin
Test ((2, 4, 6, 8, 9), 2); Test ((2, 4, 6, 8, 9), 1); Test ((2, 4, 6, 8, 9), 8); Test ((2, 4, 6, 8, 9), 10); Test ((2, 4, 6, 8, 9), 9); Test ((2, 4, 6, 8, 9), 5);
end Test_Recursive_Binary_Search; </Ada>
Iterative
<Ada> with Ada.Text_IO; use Ada.Text_IO;
procedure Test_Binary_Search is
Not_Found : exception; generic type Index is range <>; type Element is private; type Array_Of_Elements is array (Index range <>) of Element; with function "<" (L, R : Element) return Boolean is <>; function Search (Container : Array_Of_Elements; Value : Element) return Index;
function Search (Container : Array_Of_Elements; Value : Element) return Index is Low : Index := Container'First; High : Index := Container'Last; Mid : Index; begin if Container'Length > 0 then loop Mid := (Low + High) / 2; if Value < Container (Mid) then exit when Low = Mid; High := Mid - 1; elsif Container (Mid) < Value then exit when High = Mid; Low := Mid + 1; else return Mid; end if; end loop; end if; raise Not_Found; end Search;
type Integer_Array is array (Positive range <>) of Integer; function Find is new Search (Positive, Integer, Integer_Array); procedure Test (X : Integer_Array; E : Integer) is begin New_Line; for I in X'Range loop Put (Integer'Image (X (I))); end loop; Put (" contains" & Integer'Image (E) & " at" & Integer'Image (Find (X, E))); exception when Not_Found => Put (" does not contain" & Integer'Image (E)); end Test;
begin
Test ((2, 4, 6, 8, 9), 2); Test ((2, 4, 6, 8, 9), 1); Test ((2, 4, 6, 8, 9), 8); Test ((2, 4, 6, 8, 9), 10); Test ((2, 4, 6, 8, 9), 9); Test ((2, 4, 6, 8, 9), 5);
end Test_Binary_Search; </Ada> Sample output:
2 4 6 8 9 contains 2 at 1 2 4 6 8 9 does not contain 1 2 4 6 8 9 contains 8 at 4 2 4 6 8 9 does not contain 10 2 4 6 8 9 contains 9 at 5 2 4 6 8 9 does not contain 5
ALGOL 68
Iterative
MODE ELEMENT = STRING; PROC iterative binary search = ([]ELEMENT hay stack, ELEMENT needle)INT: ( INT out, low := LWB hay stack, high := UPB hay stack; WHILE low < high DO INT mid := (low+high) OVER 2; IF hay stack[mid] > needle THEN high := mid-1 ELIF hay stack[mid] < needle THEN low := mid+1 ELSE out:= mid; stop iteration FI OD; low EXIT stop iteration: out );
Recursive
PROC recursive binary search = ([]ELEMENT hay stack, ELEMENT needle)INT: ( IF LWB hay stack > UPB hay stack THEN LWB hay stack ELIF LWB hay stack = UPB hay stack THEN IF hay stack[LWB hay stack] = needle THEN LWB hay stack ELSE LWB hay stack FI ELSE INT mid := (LWB hay stack+UPB hay stack) OVER 2; IF hay stack[mid] > needle THEN recursive binary search(hay stack[:mid-1], needle) ELIF hay stack[mid] < needle THEN mid + recursive binary search(hay stack[mid+1:], needle) ELSE mid FI FI );
Test cases:
ELEMENT needle = "mister"; []ELEMENT hay stack = ("AA","Maestro","Mario","Master","Mattress","Mister","Mistress","ZZ"), test cases = ("A","Master","Monk","ZZZ"); PROC test search = (PROC([]ELEMENT, ELEMENT)INT search, []ELEMENT test cases)VOID: FOR case TO UPB test cases DO ELEMENT needle = test cases[case]; INT index = search(hay stack, needle); BOOL found = ( index <= 0 | FALSE | hay stack[index]=needle); printf(($""""g""" "b("FOUND at","near")" index "dl$, needle, found, index)) OD; test search(iterative binary search, test cases); test search(recursive binary search, test cases)
Output:
"A" near index 1 "Master" FOUND at index 4 "Monk" near index 8 "ZZZ" near index 8
BASIC
Recursive
<freebasic> FUNCTION binary_search ( array() AS Integer, value AS Integer, lo AS Integer, hi AS Integer) AS Integer
DIM middle AS Integer IF hi < lo THEN binary_search = 0 ELSE middle = (hi + lo) / 2 SELECT CASE value CASE IS < array(middle)
binary_search = binary_search(array(), value, lo, middle-1)
CASE IS > array(middle)
binary_search = binary_search(array(), value, middle+1, hi)
CASE ELSE
binary_search = middle
END SELECT END IF
END FUNCTION </freebasic>
Iterative
<freebasic> FUNCTION binary_search ( array() AS Integer, value AS Integer, lo AS Integer, hi AS Integer) AS Integer
DIM middle AS Integer WHILE lo <= hi middle = (hi + lo) / 2 SELECT CASE value CASE IS < array(middle)
hi = middle - 1
CASE IS > array(middle)
lo = middle + 1
CASE ELSE
binary_search = middle EXIT FUNCTION
END SELECT WEND binary_search = 0
END FUNCTION </freebasic>
Testing the function
The following program can be used to test both recursive and iterative version. <freebasic> SUB search (array() AS Integer, value AS Integer)
DIM idx AS Integer
idx = binary_search(array(), value, LBOUND(array), UBOUND(array)) PRINT "Value "; value; IF idx < 1 THEN PRINT " not found" ELSE PRINT " found at index "; idx END IF
END SUB
DIM test(1 TO 10) AS Integer DIM i AS Integer
DATA 2, 3, 5, 6, 8, 10, 11, 15, 19, 20 FOR i = 1 TO 10 ' Fill the test array
READ test(i)
NEXT i
search test(), 4 search test(), 8 search test(), 20 </freebasic>
Output:
Value 4 not found Value 8 found at index 5 Value 20 found at index 10
C++
Recursive
<cpp>template <class T> int binsearch(const T array[], int len, T what) {
if (len == 0) return -1; int mid = len / 2; if (array[mid] == what) return mid; if (array[mid] < what) { int result = binsearch(array+mid+1, len-(mid+1), what); if (result == -1) return -1; else return result + mid+1; } if (array[mid] > what) return binsearch(array, mid, what);
}
- include <iostream>
int main() {
int array[] = {2, 3, 5, 6, 8}; int result1 = binsearch(array, sizeof(array)/sizeof(int), 4), result2 = binsearch(array, sizeof(array)/sizeof(int), 8); if (result1 == -1) std::cout << "4 not found!" << std::endl; else std::cout << "4 found at " << result1 << std::endl; if (result2 == -1) std::cout << "8 not found!" << std::endl; else std::cout << "8 found at " << result2 << std::endl;
return 0;
}</cpp>
Iterative
<cpp>template <class T> int binSearch(const T arr[], int len, T what) {
int low = 0; int high = len - 1; while (low <= high) { int mid = (low + high) / 2; if (arr[mid] > what) high = mid - 1; else if (arr[mid] < what) low = mid + 1; else return mid; } return -1; // indicate not found
}</cpp>
Common Lisp
Iterative
<lisp>(defun binary-search (value array)
(let ((low 0) (high (1- (length array)))) (do () ((< high low) nil) (let ((middle (floor (/ (+ low high) 2)))) (cond ((> (aref array middle) value) (setf high (1- middle))) ((< (aref array middle) value) (setf low (1+ middle))) (t (return middle)))))))</lisp>
Recursive
<lisp>(defun binary-search (value array &optional (low 0) (high (1- (length array))))
(if (< high low) nil (let ((middle (floor (/ (+ low high) 2)))) (cond ((> (aref array middle) value) (binary-search value array low (1- middle))) ((< (aref array middle) value) (binary-search value array (1+ middle) high)) (t middle)))))</lisp>
D
Recursive
The range criterion is omitted because arrays in D can be slices of other arrays, so in a way every array is potentially a range.
<d>size_t binsearch(T) (T[] array, T what) {
size_t shift(size_t what, int by) { if (what == size_t.max) return size_t.max; return what + by; } if (!array.length) return size_t.max; auto mid = array.length / 2; if (array[mid] == what) return mid; if (array[mid] < what) return shift(binsearch(array[mid+1 .. $], what), mid + 1); if (array[mid] > what) return binsearch(array[0 .. mid], what);
}
import std.stdio; void main() {
auto array = [2, 3, 5, 6, 8], result1 = array.binsearch(4), result2 = array.binsearch(8); if (result1 == size_t.max) writefln("4 not found!"); else writefln("4 found at ", result1); if (result2 == size_t.max) writefln("8 not found!"); else writefln("8 found at ", result2);
}</d>
Iterative
<d>size_t binSearch(T)(T[] arr, T what) {
size_t low = 0 ; size_t high = arr.length - 1 ; while (low <= high) { size_t mid = (low + high) / 2 ; if(arr[mid] > what) high = mid - 1 ; else if(arr[mid] < what) low = mid + 1 ; else return mid ; { } return size_t.max ; // indicate not found
}</d>
Forth
This version is designed for maintaining a sorted array. If the item is not found, then then location returned is the proper insertion point for the item. This could be used in an optimized Insertion sort, for example.
defer (compare) ' - is (compare) \ default to numbers : cstr-compare ( cstr1 cstr2 -- <=> ) \ counted strings swap count rot count compare ; : mid ( u l -- mid ) tuck - 2/ -cell and + ; : bsearch ( item upper lower -- where found? ) rot >r begin 2dup > while 2dup mid dup @ r@ (compare) dup while 0< if nip cell+ ( upper mid+1 ) else rot drop swap ( mid lower ) then repeat drop nip nip true else max ( insertion-point ) false then r> drop ;
create test 2 , 4 , 6 , 9 , 11 , 99 , : probe ( n -- ) test 5 cells bounds bsearch . @ . cr ; 1 probe \ 0 2 2 probe \ -1 2 3 probe \ 0 4 10 probe \ 0 11 11 probe \ -1 11 12 probe \ 0 99
Fortran
Recursive
In ISO Fortran 90 or later use a RECURSIVE function and ARRAY SECTION argument:
recursive function binarySearch_R (a, value) result (bsresult) real, intent(in) :: a(:), value integer :: bsresult, mid mid = size(a)/2 + 1 if (size(a) == 0) then bsresult = 0 ! not found else if (a(mid) > value) then bsresult= binarySearch_R(a(:mid-1), value) else if (a(mid) < value) then bsresult = binarySearch_R(a(mid+1:), value) if (bsresult /= 0) then bsresult = mid + bsresult end if else bsresult = mid ! SUCCESS!! end if end function binarySearch_R
Iterative
In ISO Fortran 90 or later use an ARRAY SECTION POINTER:
function binarySearch_I (a, value) integer :: binarySearch_I real, intent(in), target :: a(:) real, intent(in) :: value real, pointer :: p(:) integer :: mid, offset p => a binarySearch_I = 0 offset = 0 do while (size(p) > 0) mid = size(p)/2 + 1 if (p(mid) > value) then p => p(:mid-1) else if (p(mid) < value) then offset = offset + mid p => p(mid+1:) else binarySearch_I = offset + mid ! SUCCESS!! return end if end do end function binarySearch_I
Haskell
The algorithm itself, parametrized by an "interrogation" predicate p in the spirit of the explanation above:
binarySearch :: Integral a => (a -> Ordering) -> (a, a) -> Maybe a binarySearch p (low,high) | high < low = Nothing | otherwise = let mid = (low + high) `div` 2 in case p mid of LT -> binarySearch p (low, mid-1) GT -> binarySearch p (mid+1, high) EQ -> Just mid
Application to an array:
import Data.Array binarySearchArray :: (Ix i, Integral i, Ord e) => Array i e -> e -> Maybe i binarySearchArray a x = binarySearch p (bounds a) where p m = x `compare` (a ! m)
The algorithm uses tail recursion, so the iterative and the recursive approach are identical in Haskell (the compiler will convert recursive calls into jumps).
Java
Iterative
<java>... //check will be the number we are looking for //nums will be the array we are searching through int hi = nums.length - 1; int lo = 0; int guess = (hi + lo) / 2; while((nums[guess] != check) && (hi > lo)){
if(nums[guess] > check){ hi = guess - 1; }else if(nums[guess] < check){ lo = guess + 1; } guess = (hi + lo) / 2;
} if(hi < lo){
System.out.println(check + " not in array");
}else{
System.out.println("found " + nums[guess] + " at index " + guess);
} ...</java>
Recursive
<java>public static void main(String[] args){
int[] searchMe; int someNumber; ... int index = binarySearch(searchMe, someNumber, 0, searchMe.length); System.out.println(someNumber + ((index == -1) ? " is not in the array" : (" is at index " + index))); ...
}
public static int binarySearch(int[] nums, int check, int lo, int hi){
if(hi < lo){ return -1; //impossible index for "not found" } int guess = (hi + lo) / 2; if(nums[guess] > check){ return binarySearch(nums, check, lo, guess - 1); }else if(nums[guess]<check){ return binarySearch(nums, check, guess + 1, hi); } return guess;
}</java>
Logo
to bsearch :value :a :lower :upper if :upper < :lower [output []] localmake "mid int (:lower + :upper) / 2 if item :mid :a > :value [output bsearch :value :a :lower :mid-1] if item :mid :a < :value [output bsearch :value :a :mid+1 :upper] output :mid end
MAXScript
Iterative
fn binarySearchIterative arr value = ( lower = 1 upper = arr.count while lower <= upper do ( mid = (lower + upper) / 2 if arr[mid] > value then ( upper = mid - 1 ) else if arr[mid] < value then ( lower = mid + 1 ) else ( return mid ) ) -1 ) arr = #(1, 3, 4, 5, 6, 7, 8, 9, 10) result = binarySearchIterative arr 6
Recursive
fn binarySearchRecursive arr value lower upper = ( if lower == upper then ( if arr[lower] == value then ( return lower ) else ( return -1 ) ) mid = (lower + upper) / 2 if arr[mid] > value then ( return binarySearchRecursive arr value lower (mid-1) ) else if arr[mid] < value then ( return binarySearchRecursive arr value (mid+1) upper ) else ( return mid ) ) arr = #(1, 3, 4, 5, 6, 7, 8, 9, 10) result = binarySearchRecursive arr 6 1 arr.count
OCaml
Recursive
<ocaml>let rec binary_search a value low high =
if high = low then if a.(low) = value then low else raise Not_found else let mid = (low + high) / 2 in if a.(mid) > value then binary_search a value low (mid - 1) else if a.(mid) < value then binary_search a value (mid + 1) high else mid</ocaml>
Output:
# let arr = [|1; 3; 4; 5; 6; 7; 8; 9; 10|];; val arr : int array = [|1; 3; 4; 5; 6; 7; 8; 9; 10|] # binary_search arr 6 0 (Array.length arr - 1);; - : int = 4 # binary_search arr 2 0 (Array.length arr - 1);; Exception: Not_found.
OCaml supports proper tail-recursion; so this is effectively the same as iteration.
Perl
Iterative
<perl>sub binary_search {
($array_ref, $value, $left, $right) = @_; while ($left <= $right) { $middle = ($right + $left) / 2; if ($array_ref->[$middle] == $value) { return 1; } if ($value < $array_ref->[$middle]) { $right = $middle - 1; } else { $left = $middle + 1; } } return 0;
}</perl>
Recursive
<perl>sub binary_search {
($array_ref, $value, $left, $right) = @_; if ($right < $left) { return 0; } $middle = ($right + $left) / 2; if ($array_ref->[$middle] == $value) { return 1; } if ($value < $array_ref->[$middle]) { binary_search($array_ref, $value, $left, $middle - 1); } else { binary_search($array_ref, $value, $middle + 1, $right); }
}</perl>
PHP
Iterative
<php> function binary_search( $secret, $start, $end ) {
do { $guess = $start + ( ( $end - $start ) / 2 );
if ( $guess > $secret ) $end = $guess;
if ( $guess < $secret ) $start = $guess;
} while ( $guess != $secret );
return $guess;
} </php>
Recursive
<php> function binary_search( $secret, $start, $end ) {
$guess = $start + ( ( $end - $start ) / 2 );
if ( $guess > $secret ) return (binary_search( $secret, $start, $guess ));
if ( $guess < $secret ) return (binary_search( $secret, $guess, $end ) );
return $guess;
} </php>
Pop11
Iterative
define BinarySearch(A, value); lvars low = 1, high = length(A), mid; while low <= high do (low + high) div 2 -> mid; if A(mid) > value then mid - 1 -> high; elseif A(mid) < value then mid + 1 -> low; else return(mid); endif; endwhile; return("not_found"); enddefine; /* Tests */ lvars A = {2 3 5 6 8}; BinarySearch(A, 4) => BinarySearch(A, 5) => BinarySearch(A, 8) =>
Recursive
define BinarySearch(A, value); define do_it(low, high); if high < low then return("not_found"); endif; (low + high) div 2 -> mid; if A(mid) > value then do_it(low, mid-1); elseif A(mid) < value then do_it(mid+1, high); else mid; endif; enddefine; do_it(1, length(A)); enddefine;
Python
Iterative
<python>def binary_search(l, value):
low = 0 high = len(l)-1 while low <= high: mid = (low+high)//2 if l[mid] > value: high = mid-1 elif l[mid] < value: low = mid+1 else: return mid return -1</python>
Recursive
<python>def binary_search(l, value, low = 0, high = -1):
if(high == -1): high = len(l)-1 if low == high: if l[low] == value: return low else: return -1 mid = (low+high)//2 if l[mid] > value: return binary_search(l, value, low, mid-1) elif l[mid] < value: return binary_search(l, value, mid+1, high) else: return mid</python>
Scheme
Recursive
<scheme>(define (binary-search value vector)
(let helper ((low 0) (high (- (vector-length vector) 1))) (if (< high low) #f (let ((middle (quotient (+ low high) 2))) (cond ((> (vector-ref vector middle) value) (helper low (- middle 1))) ((< (vector-ref vector middle) value) (helper (+ middle 1) high)) (else middle))))))</scheme>
Example:
> (binary-search 6 '#(1 3 4 5 6 7 8 9 10)) 4 > (binary-search 2 '#(1 3 4 5 6 7 8 9 10)) #f
Scheme requires proper tail-recursion; so this is effectively the same as iteration.
Seed7
Iterative
const func integer: binarySearchIterative (in array elemType: arr, in elemType: aKey) is func result var integer: result is 0; local var integer: low is 1; var integer: high is 0; var integer: middle is 0; begin high := length(arr); while result = 0 and low <= high do middle := low + (high - low) div 2; if aKey < arr[middle] then high := pred(middle); elsif aKey > arr[middle] then low := succ(middle); else result := middle; end if; end while; end func;
Recursive
const func integer: binarySearch (in array elemType: arr, in elemType: aKey, in integer: low, in integer: high) is func result var integer: result is 0; begin if low <= high then result := (low + high) div 2; if aKey < arr[result] then result := binarySearch(arr, aKey, low, pred(result)); # search left elsif aKey > arr[result] then result := binarySearch(arr, aKey, succ(result), high); # search right end if; end if; end func; const func integer: binarySearchRecursive (in array elemType: arr, in elemType: aKey) is return binarySearch(arr, aKey, 1, length(arr));
UnixPipes
Parallel
splitter() { a=$1; s=$2; l=$3; r=$4; mid=$(expr ${#a[*]} / 2); echo $s ${a[*]:0:$mid} > $l echo $(($mid + $s)) ${a[*]:$mid} > $r }
bsearch() { (to=$1; read s arr; a=($arr); test ${#a[*]} -gt 1 && (splitter $a $s >(bsearch $to) >(bsearch $to)) || (test "$a" -eq "$to" && echo $a at $s) ) }
binsearch() { (read arr; echo "0 $arr" | bsearch $1) }
echo "1 2 3 4 6 7 8 9" | binsearch 6