35.md

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

:pencil2:题目描述

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

:pencil2:题目实例

​

---

:pencil2:题目分析

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

---

:pencil2:最终实现代码

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

---

联系

​