Iterative binary search

Question

Binary search is an algorithm that looks for an element in a sorted data-structure by constantly dividing the search space in half.

Rosetta Code

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.

Wikipedia

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

Clarifications

• Example of calling the function/lambda/macro should be included, but don't count those chars!
• Output should be > -1 if found, and <=-1 otherwise
• 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.

Example

> binary_search([1,3,5,6,7,8,8,10], 5);
4
> binary_search([1,3,5,6,7,8,8,10], 543);
-1

Answer 1

JavaScript (94 bytes)

(a,e)=>{u=a.length,m=0;for(l=0;l<=u;)e>a[m=(l+u)>>1]?l=m+1:u=e==a[m]?-2:m-1;return u==-2?m:-1}

Expanded out a little so you can see what's going on:

function binary_search(array, elem) {
    let u = array.length, m;
    for (let l = 0; l <= u;)
        if (elem > array[(m = (l + u) >> 1)]) l = m + 1;
        else u = (elem == array[m]) ? -2 : m - 1;
    return (u == -2) ? m : -1;
}

Example usage:

> a = [1,2,3,4,5,6,7,8,9,10]
> binary_search(a, 5)
4
> binary_search(a, 15)
-1

Answer 2

C – 119 115 bytes

Iterative solution at 119 bytes:

f(a,x,l,h)int*a,x,l,h;{while(l<h){int m=(h+l)/2;if(a[m]>x)h=m;else if(a[m]<x)l=m+1;else return m;}return a[l]==x?l:-1;}

Recursive solution at 115 bytes:

f(a,x,l,h)int*a,x,l,h;{if(l==h)return a[l]==x?l:-1;int m=(h+l)/2;return a[m]>x?f(a,x,l,m):(a[m]<x?f(a,x,m+1,h):m);}

You can precede with int to prevent compiler warnings or if you're using gcc compile with -Wno-implicit-int. Sample:

#include <stdio.h>

f(a,x,l,h)int*a,x,l,h;{while(l<h){int m=(h+l)/2;if(a[m]>x)h=m;else if(a[m]<x)l=m+1;else return m;}return a[l]==x?l:-1;}

int main()
{
    int x, a[] = {-10, -8, -6, -4, -2, 0, 2, 4, 6, 8, 10};

    for (x = -15; x <= 15; x++)
        printf("%d\t%d\n", x, f(a, x, 0, 10));

    return 0;
}

Answer 3

Python 112 bytes

def b(A,k):
 l,h=0,len(A)
 while l<h:
  m=(l+h)/2
  if A[m]>k:h=m
  elif A[m]<k:l=m+1
  else:return m
 return -1

Example:

print b([1,3,5,6,7,8,8,10], 5)

2

Answer 4

AutoIt, 92 bytes

This function binary searches an array in-memory and replaces it with an integer holding the index (or -1 if not found). Array needs to be sorted to work with the binary search:

#include <Array.au3>
Func b(ByRef $a,$n)
_ArraySort($a)
$a=_ArrayBinarySearch($a,$n)
EndFunc

Testing:

Local $a = [1,2,3,4,5,6,7,8,9,10]
b($a,5)
ConsoleWrite($a & @LF)

Output: 4

Answer 5

C++14, 87 85 bytes

#include<algorithm>
[](int i,auto v){return std::binary_search(begin(v),end(v),i)-1;}

Assumes a sorted data structure which has iterators as input.

Example:

#include<algorithm>
#include<iostream>

auto f = [](int i, auto v){ return std::binary_search(begin(v), end(v), i) - 1; };

int main()
{
    std::vector<int> v = { 1, 2, 3, 4, 5 };

    std::cout << f(3, v);
}

Answer 6

Prolog, 146 bytes

I made the assumption that a program returning easy to understand truthy/falsy values is OK, as adding code just to return -1/1 instead of true/false in a code-golf challenge seems counter-productive.
So the program returns true if the value is present in the list, otherwise false.

s(F,S,L):-append(F,S,L),length(F,G),length(S,T),T>=G,T-G<2.
c(L,X):-s(_,[X|_],L).
c(L,X):-s(_,[M|T],L),X>M,c(T,X).
c(L,X):-s(F,[_|_],L),c(F,X).

How it works

s(F,S,L):-append(F,S,L),length(F,G),length(S,T),T>=G,T-G<2.

Helper function that takes the list L and splits it in the middle into the lists F and S where F is the lower part of the list. If L has an odd number of elements, S is one element larger than F.

c(L,X):-s(_,[X|_],L).

Succeeds if the sought after element X is in the middle of list L.

c(L,X):-s(_,[M|T],L),X>M,c(T,X).

Checks for X in the higher part of the list if X is bigger than the middle element of list L.

c(L,X):-s(F,[_|_],L),c(F,X).

Checks for X in the lower part of the list if X is smaller than the middle element of list L.
As the previous predicates are checked first we can save a few bytes by not doing a comparison here.

Examples:

> c([1,3,5,6,7,8,8,10],5).
true

> c([1,3,5,6,7,8,8,10],543).
false

Answer 7

Common Lisp, 142 143 bytes

Having seen some of the comments about recursive vs iterative, I'd point out that in any implementation with tail-call optimization, the second (original) solution is iterative.

pure iterative, with do loop (143):

(lambda(a e)(do((l 0)(h(length a)))((<= h l)-1)(let*((m(ash(+ h l)-1))(x(aref a m)))(if(= x e)(return m)(if(< e x)(setf h m)(setf l(1+ m)))))))

(lambda (a e)
    (do ((l 0)
         (h (length a)))
        ((<= h l) -1)
      (let* ((m (ash (+ h l) -1))
             (x (aref a m)))
        (if (= x e)
            (return m)
            (if (< e x)
                (setf h m)
                (setf l (1+ m)))))))

recursive (142)

(defun b(a e &optional(l 0)(h(length a)))(if(<= h l)-1(let*((m(ash(+ h l)-1))(x(aref a m)))(if(= x e)m(if(< e x)(b a e l m)(b a e(1+ m)h))))))

(defun b (a e &optional (l 0) (h (length a)))
  (if (<= h l) -1
      (let* ((m (ash (+ h l) -1))
             (x (aref a m)))
        (if (= x e) m
            (if (< e x)
                (b a e l m)
                (b a e (1+ m) h))))))

CL-USER> (loop with array = #(1 3 5 6 7 8 8 10)
            for element in '(1 7 5 3 2 4 6)
            collect (b array element))
(0 4 2 1 -1 -1 3)