Leetcode基础刷题之PHP解析(二分查找之33,35)


2019-5-8 期二  

Leetcode基础刷题之PHP解析(108,513)

814c9c2c37e87dc7b4af730217a90ad7.png

先来基础版的。给定一个已排序的数组,给一个指定值,返回值在数组中的下标,如果不存在,返回把值插入到数组之后的下标。

利用二分查找,定义两个下标,初始的时候一个指向数组开始位置一个指向数组最后位置,每次取数组中间,等于直接返回下标,如果中间数小于给定值,那么就把范围缩小成中间数之后的位置,否则把范围缩小成中间数之前的位置。这里中间数为了防止数值过大可以使用位运算来求。

 /**
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer
     */
    function searchInsert($nums, $target) {
        $l=0;
        $r=count($nums)-1;
        while($l<=$r){
            // $middle=floor(($l+$r)/2);
            //$middle=$l+floor(($r-$l)/2);
            $middle=$l+(($r-$l)>>1);
            if($nums[$middle]==$target) return $middle;
            if($nums[$middle]<$target){
                $l=$middle+1;
            }else{
                $r=$middle-1;
            }
            
        }
        return $l;
    }



54c033f8360256a2d69f406ec464c011.png

一个有序数组在不确定的位置进行了旋转,让我们 来求旋转后给定值在当前数组的下标位置,如果没有返回-1.

这道题因为本身的数组是有序的,只是在哪个点上发生了旋转的操作,这就造成了数组一半是有序的,我们取数组的中间数做判断,如果中间数小于数组的右半边,说明中间到右半边这一块是有序的,否则左半边就是有序的,然后根据给定值以及确定的半边有序区域的首尾的位置,继续缩小搜索的位置。

 /**
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer
     */
    function search($nums, $target) {
        $l=0;
        $r=count($nums)-1;
       while($l<=$r){
           $middle=$l+(($r-$l)>>1);
           if($nums[$middle]===$target) return $middle;
           else if($nums[$middle]<$nums[$r]){
               if($nums[$middle]<$target && $nums[$r]>=$target) $l=$middle+1;
               else $r=$middle-1;
           }else{
               if($nums[$l]<=$target && $nums[$middle]>$target) $r=$middle-1;
               else $l=$middle+1;
           }
       }
        return -1;
    }

Github整理地址:https://github.com/wuqinqiang/leetcode-php


Vote Vote Cancel Collect Collect Cancel

<< 上一篇: Leetcode PHP题解--D55 429. N-ary Tree Level Order Traversal

>> 下一篇: Leetcode PHP题解--D56 637. Average of Levels in Binary Tree