Notice: Undefined index: key in /home/worker/data/www/liuzimu-blogs/usr/plugins/MysqlRun/Plugin.php on line 138 算法入门-二分法 - liuzimu ‘ blog
  • Home
  • Notice: Undefined index: key in /home/worker/data/www/liuzimu-blogs/usr/plugins/MysqlRun/Plugin.php on line 138
  • archives
  • Github

  • Notice: Undefined index: key in /home/worker/data/www/liuzimu-blogs/usr/plugins/MysqlRun/Plugin.php on line 138
  • Notice: Undefined index: key in /home/worker/data/www/liuzimu-blogs/usr/plugins/MysqlRun/Plugin.php on line 138

算法入门-二分法

leetcode 704

leetcode 704

class Solution {

    /**
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer
     */
    function search($nums, $target) {
        $hight = count($nums) - 1;
        $low = 0;

        while($low <= $hight ) {
            $mid = floor(($hight - $low) / 2) + $low; //5
            if($nums[$mid] === $target) {
                return $mid;
            } else if($nums[$mid] > $target) {
                $hight = $mid - 1;
            } else {
                $low = $mid + 1;
            }
        }

        return -1;
    }
}

leetcode 278

leetcode 278


class Solution extends VersionControl {
    /**
     * @param Integer $n
     * @return Integer
     */
    function firstBadVersion($n) {

        if($n === 1) {
            return 1;
        }

        $low = 1;
        $hight = $n;

        while ($low < $hight) {
            $mid = floor($low + ($hight - $low) / 2); 
            if($this->isBadVersion($mid)) {
                $hight = $mid;
            } else {
                $low = $mid + 1;
            }
        }

        return $low;
    }
}

leetcode 35

leetcode 35

class Solution {

    /**
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer
     */
    function searchInsert($nums, $target) {
        $low = 0;
        $hight = count($nums) - 1;

        while ($low <= $hight) {
            $mid = floor($low + ($hight - $low) / 2);
            if($nums[$mid] == $target) {
                return $mid;
            } else if($nums[$mid] > $target) {
                $hight = $mid - 1;
                $lastOffset = false;
            } else {
                $low = $mid + 1;
                $lastOffset = true;
            }
        }

        $lastOffset && $mid = $mid + 1;

        return $mid;
    }
}

本文链接:

http://zimu.devorz.com/archives/25/
1 + 3 =
快来做第一个评论的人吧~