# Iterative binary search

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

• Does our implementation have to be exactly as binary search does it? Does is have to be logarithmic time? – xnor Nov 13 '15 at 6:27
• Can the list have repeats? Are the entries whole numbers? You should give an example that doesn't have all consecutive values. – xnor Nov 13 '15 at 7:01
• @xnor: Thanks for your comments, clarified. – A T Nov 13 '15 at 8:45
• 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. – Dennis Nov 13 '15 at 13:30
• 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. – Dennis Nov 13 '15 at 13:30

### 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


# 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;
}

• -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 – A T Nov 13 '15 at 11:52
• @AT – Added at a penalty of 4 additional bytes! – user15259 Nov 13 '15 at 12:19
• 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 – A T Nov 13 '15 at 12:30

# 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

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

## 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

• 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!!! – A T Nov 13 '15 at 8:55
• kaspersky declares autoit as a trojan unfortunately for developers – Abr001am Nov 18 '15 at 14:43

# 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);
}

• 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!!! – A T Nov 13 '15 at 8:55

# 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

• Nice one. Sure, happy to relax the -1 condition. Haven't seen Prolog since college! :P – A T Nov 19 '15 at 2:21

## 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)

• Nice work, haven't seen Lisp in ages! - Also find it amusing that the iterative vs recursive is 1 character apart… +1 – A T Nov 19 '15 at 2:19