Binary search: Difference between revisions
Content added Content deleted
(Add Seed7 example) |
m (Added to <10 category, stop separating task and examples with headers) |
||
| Line 1: | Line 1: | ||
{{task}}[[Category:Recursion]] |
[[Category:Less Than 10 Examples]]{{task}}[[Category:Recursion]] |
||
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. |
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. |
||
| Line 5: | Line 5: | ||
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. |
||
=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 [http://en.wikipedia.org/wiki/Binary_search the wikipedia]): |
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 [http://en.wikipedia.org/wiki/Binary_search the wikipedia]): |
||
| Line 39: | Line 37: | ||
} |
} |
||
=Examples= |
|||
=={{header|D}}== |
=={{header|D}}== |
||
Recursive version: |
Recursive version: |
||