Binary search is an algorithm that looks for an element in a sorted data-structure by constantly dividing the search space in half.
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.
In computer science, a binary search or half-interval search algorithm finds the position of a target value within a sorted array. The binary search algorithm can be classified as a dichotomic divide-and-conquer search algorithm and executes in logarithmic time.
Smallest # of bytes wins
- Example of calling the function/lambda/macro should be included, but don't count those chars!
- Output should be
> -1if found, and
import binary_search(20 bytes) DOES NOT count!
- Implementation should run in O(log n), as algorithm dictates
Also see the code-golf StackExchange FAQ.
> binary_search([1,3,5,6,7,8,8,10], 5); 4 > binary_search([1,3,5,6,7,8,8,10], 543); -1