d language dlang binary search lower_bound upper_bound

size_t lowerBound(long[] arr, long value)
{
  size_t first = 0;
  size_t count = arr.length;
  while (count > 0)
  {
    size_t step = count / 2;
    size_t mid  = first + step;
    if (arr[mid] < value)
    {
      first = mid + 1;
      count -= step + 1;
    }
    else
    {
      count = step;
    }
  }
  return first;
}

import std.stdio;

void main()
{
  long[] a = [1, 3, 5, 7, 9];
  size_t idx;

  idx = lowerBound(a, 5);
  writeln(idx);        // 2

  idx = lowerBound(a, 6);
  writeln(idx, " → ", a[idx]); // 3 → 7

  idx = lowerBound(a, 10);
  writeln(idx);        // 5 (i.e. past the end)
}

size_t upperBound(long[] arr, long value)
{
  size_t first = 0;
  size_t count = arr.length;
  while (count > 0)
  {
    size_t step = count / 2;
    size_t mid   = first + step;
    if (value >= arr[mid])
    {
      first = mid + 1;
      count -= step + 1;
    }
    else
    {
      count = step;
    }
  }
  return first;
}

import std.stdio;

void main()
{
  long[] a = [1, 3, 5, 7, 9];

  writeln(upperBound(a, 5));  // 3
  writeln(upperBound(a, 6));  // 3
  writeln(upperBound(a, 9));  // 5
  writeln(upperBound(a, 0));  // 0
}

Vicfred/dlang_binary_search_lowerbound_upperbound.md