迭代二值搜索

Question

二进制搜索是一种算法，它通过不断地将搜索空间分成两部分来寻找排序数据结构中的元素。

罗塞塔码

二进制搜索将值范围分成两部分，并继续缩小搜索范围，直到找到未知值为止。这是“分而治之”算法的经典例子。

维基百科

在计算机科学中，二进制搜索或半间隔搜索算法在排序数组中查找目标值的位置。二进制搜索算法可分为二次分而治之搜索算法，在对数时间内执行。

最小字节数获胜

Clarifications

• 应该包括调用函数/lambda/宏的示例，但是不要计算那些字符！
• 如果找到输出，则输出应为> -1，否则为<=-1。
• import binary_search (20个字节)不算！
• 实现应该在O(log )中运行，就像算法要求的那样

还可以看到代码-高尔夫StackExchange常见问题。

示例

> 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字节)

(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}

扩展一点，这样你就能看到发生了什么：

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

示例用法：

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

Answer 2

Python 112个字节

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

示例：

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

2

Answer 3

Prolog，146个字节

我假设返回容易理解的真实/错误值的程序是可以的，因为在代码-高尔夫挑战中添加代码只返回-1/1，而不是真/假，这似乎适得其反。

因此，如果该值存在于列表中，则程序返回true，否则为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).

它是如何工作的

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

帮助者函数，取列表L，在中间将其分割成列表F和S，其中F是列表的下半部分。如果L有一个奇数的元素，S是一个比F大的元素。

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

如果所需元素X位于列表L的中间，则成功。

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

如果X大于列表L的中间元素，则在列表的较高部分检查X。

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

如果X小于列表L的中间元素，则检查列表下部的X。

由于前面的谓词是首先检查的，我们可以在这里不做比较来保存几个字节。

示例：

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

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