binary search

gistfile1.d

import std.stdio;
import std.range;
import std.algorithm;

void main()
{
  writeln([3, 1, 6, 2].exists(6));      // true
  writeln([2, 3, 4, 5, 3].exists(6));   // false
}

bool exists(int[] xs, int needle)
{
  bool f(int[] ys)
  {
    if (ys.empty) return false;

    auto i = ys.length / 2;

    if (ys[i] < needle) return f(ys[(i + 1)..$]);
    if (needle < ys[i]) return f(ys[0..i]);

    return true;
  }

  return f(xs.sort);
}

unittest
{
  auto ns1 = [2, 5, 3, 4];
  auto m1 = 5;
  assert(!ns1.find(m1).empty == ns1.exists(m1));

  auto ns2 = [2, 5, 3, 4, 1];
  auto m2 = 7;
  assert(!ns2.find(m2).empty == ns2.exists(m2));

  auto ns3 = [1];
  auto m3 = 1;
  assert(!ns3.find(m3).empty == ns3.exists(m3));

  auto ns4 = [1];
  auto m4 = 2;
  assert(!ns4.find(m4).empty == ns4.exists(m4));
}