ThreeSumN2logN.php

function binarySearchRecursiveImpl(array $array, $find, $left, $right) {
  if (count($array) < 1 || $left > $right) {
    return -1;
  }
  $mid = floor(($left + $right) / 2);
  if ($find == $array[$mid]) {
    return $mid;
  }
  return $find > $array[$mid] ? 
    binarySearchRecursiveImpl($array, $find, $mid+1, $right) :
    binarySearchRecursiveImpl($array, $find, $left, $mid-1);
}
    
function threeSumN2logn($data) {
  $count = 0;
  if (count($data) < 3) {
    return $count;
  }                  
  for ($i = 0; $i < count($data); $i++) {
    for ($j = $i+1; $j < count($data); $j++) { 
      $lookup = ((int) $data[$i] + (int) $data[$j]) * -1;
      $mid = binarySearchRecursiveImpl($data, $lookup, $j+1, count($data)-1);
      if ($mid >= 0) {
        $count++;
      } 
    }
  }
  return $count;
}