Simple Binary Search implementation to find an unbounded integer.

FindX.php

<?php


class FindX {

  function __construct($x) {
    $this->x = $x;
  }

  /**
   * Find X where X is an unbounded integer greater than 0.
   *
   * @return integer
   */
  public function execute() {
    $max = $this->findUpperLimit();
    return $this->binarySearch(0, $max);
  }

  /**
   * Determine if a number is less than X.
   *
   * @param integer $i
   *
   * @return boolean
   */
  protected function isLessThanX($i) {
    return $i < $this->x;
  }

  /**
   * Determine if the given number is X.
   *
   * @param integer $i
   *
   * @return boolean
   */
  protected function equalsX($i) {
    return $this->isLessThanX($i-1) && !$this->isLessThanX($i);
  }

  /**
   * Determines a usability upper bound.
   */
  protected function findUpperLimit() {
    for ($i = 2; $this->isLessThanX($i); $i *= $i);
    return $i;
  }
  
  /**
   * Find X within the boundary conditions.
   *
   * @param integer $min
   * @param integer $max
   *
   * @return integer|boolean
   *   If X cannot be found, returns FALSE.
   */
  protected function binarySearch($min, $max) {
    // If $max and $min reverse, the target is unfindable.
    if ($max < $min) {
      return FALSE;
    }
    $mid = $this->midpoint($min, $max);

    if ($this->equalsX($mid)) {
      return $mid;
    }
    // We know $mid is not X, so increment to save extra search passes on large
    // data sets.
    elseif ($this->isLessThanX($mid)) {
      return $this->binarySearch($mid+1, $max);
    }
    return $this->binarySearch($min, $mid-1);
  }

  /**
   * Find the midpoint between two integers.
   *
   * @return integer
   */
  protected function midpoint($min, $max) {
    return floor($min + ($max - $min) / 2);
  }
}