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

2019-5-8 星期二  开始吧

上一题链接Leetcode基础刷题之PHP解析(108,513)

题目描述

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

题目分析

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

 /**
     * @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;
    }

一个有序数组在不确定的位置进行了旋转，让我们 来求旋转后给定值在当前数组的下标位置，如果没有返回-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