33.md

2019-05-08 吴亲库里 库里的深夜食堂

:pencil2:题目描述

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

:pencil2:题目实例

​

---

:pencil2:题目分析

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

---

:pencil2:最终实现代码

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

---

联系

​