4
\$\begingroup\$

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
\$\endgroup\$
6
  • 4
    \$\begingroup\$ Does our implementation have to be exactly as binary search does it? Does is have to be logarithmic time? \$\endgroup\$ – xnor Nov 13 '15 at 6:27
  • 3
    \$\begingroup\$ Can the list have repeats? Are the entries whole numbers? You should give an example that doesn't have all consecutive values. \$\endgroup\$ – xnor Nov 13 '15 at 7:01
  • \$\begingroup\$ @xnor: Thanks for your comments, clarified. \$\endgroup\$ – A T Nov 13 '15 at 8:45
  • 5
    \$\begingroup\$ Regarding your comments on some of the answers: 1. That's not a FAQ; it's the code-golf tag wiki. Also, there are two ordered lists on that page, and both have a 5th item. 2. Have built-in-to-some-languages solutions excluded is a suggestion that you exclude built-ins when writing up your challenge. That's all it is: a suggestion, not a rule. Built-ins are not forbidden by default, and the second revision of your question doesn't include the word implementation. \$\endgroup\$ – Dennis Nov 13 '15 at 13:30
  • 6
    \$\begingroup\$ 3. Last but not least, please consider using less exclamation points, less bold text and a different tone when dealing with submissions to your challenge. It's a little off-putting, and certainly no incentive to participate in one of your challenges. \$\endgroup\$ – Dennis Nov 13 '15 at 13:30
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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;
}
\$\endgroup\$
3
  • \$\begingroup\$ -Wno-implicit-int is our friend :) - Nice little solution you've written, but unfortunately it's recursive… if you get the chance an iterative equivalent would be great! - Otherwise I'll have to 1 up you with a C solution of my own :3 \$\endgroup\$ – A T Nov 13 '15 at 11:52
  • 1
    \$\begingroup\$ @AT – Added at a penalty of 4 additional bytes! \$\endgroup\$ – user15259 Nov 13 '15 at 12:19
  • \$\begingroup\$ Looking good! - +1 - Though that initialization is a bit weird, I feel that a swap to C++ would save 4 bytes right off the bat :O \$\endgroup\$ – A T Nov 13 '15 at 12:30
2
\$\begingroup\$

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

\$\endgroup\$
1
  • \$\begingroup\$ Rather neat! - I keep trying to improve it, but haven't saved a character yet >.< - +1 \$\endgroup\$ – A T Nov 13 '15 at 13:45
1
\$\begingroup\$

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

\$\endgroup\$
2
  • \$\begingroup\$ I see no implementation! - See 5 in this site's FAQ. Also I've updated the question to [more] explicitly say that import binary_search doesn't count!!! \$\endgroup\$ – A T Nov 13 '15 at 8:55
  • \$\begingroup\$ kaspersky declares autoit as a trojan unfortunately for developers \$\endgroup\$ – Abr001am Nov 18 '15 at 14:43
1
\$\begingroup\$

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);
}
\$\endgroup\$
1
  • \$\begingroup\$ I see no implementation! - See 5 in this site's FAQ. Also I've updated the question to [more] explicitly say that import binary_search doesn't count!!! \$\endgroup\$ – A T Nov 13 '15 at 8:55
1
\$\begingroup\$

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
\$\endgroup\$
1
  • \$\begingroup\$ Nice one. Sure, happy to relax the -1 condition. Haven't seen Prolog since college! :P \$\endgroup\$ – A T Nov 19 '15 at 2:21
1
\$\begingroup\$

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)
\$\endgroup\$
1
  • \$\begingroup\$ Nice work, haven't seen Lisp in ages! - Also find it amusing that the iterative vs recursive is 1 character apart… +1 \$\endgroup\$ – A T Nov 19 '15 at 2:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.