Binary search: Difference between revisions
m (→{{header|D}}: +iterative) |
(Using wp:, syntax highlighting) |
||
Line 6: | Line 6: | ||
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. |
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 [ |
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 [[wp:Binary_search|the wikipedia]]): |
||
'''Recursive Pseudocode''': |
'''Recursive Pseudocode''': |
||
Line 42: | Line 42: | ||
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. |
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=== |
===Iterative=== |
||
<d>size_t binSearch(T)(T[] arr, T what) { |
<d>size_t binSearch(T)(T[] arr, T what) { |
||
Line 143: | Line 143: | ||
===Iterative=== |
===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=== |
===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> |
|||
} |
|||
=={{header|MAXScript}}== |
=={{header|MAXScript}}== |
||
Line 250: | Line 250: | ||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
===Iterative=== |
===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=== |
===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> |
|||
} |
|||
=={{header|PHP}}== |
=={{header|PHP}}== |
||
===Iterative=== |
===Iterative=== |
||
< |
<php> |
||
function binary_search( $secret, $start, $end ) |
function binary_search( $secret, $start, $end ) |
||
{ |
{ |
||
Line 302: | Line 302: | ||
return $guess; |
return $guess; |
||
} |
} |
||
</ |
</php> |
||
===Recursive=== |
===Recursive=== |
||
< |
<php> |
||
function binary_search( $secret, $start, $end ) |
function binary_search( $secret, $start, $end ) |
||
{ |
{ |
||
Line 317: | Line 317: | ||
return $guess; |
return $guess; |
||
} |
} |
||
</ |
</php> |
||
=={{header|Python}}== |
=={{header|Python}}== |
||
===Iterative=== |
===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=== |
===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> |
|||
=={{header|Seed7}}== |
=={{header|Seed7}}== |
Revision as of 20:54, 25 March 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 }
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
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>
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
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>
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>
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));