Binary search: Difference between revisions
(→Examples: Fixed heading level for pseudocode iterative, PHP template use) |
(Haskell solution) |
||
Line 42: | Line 42: | ||
return not_found |
return not_found |
||
} |
} |
||
=={{header|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). |
|||
=={{header|Java}}== |
=={{header|Java}}== |
Revision as of 13:51, 8 November 2007
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.
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.
This is an example of a binary search.
Task
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):
Examples
Pseudocode
Recursive
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
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 }
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
... //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); } ...
Recursive
public static int binarySearch(int[] nums, int check, int lo, int hi){ if(hi < lo){ return -1; } 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; }
PHP
Iterative
This approach uses a loop.
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; }
Recursive
This approach uses recursion.
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; }