二分查找实现

 1 func search( nums []int ,  target int ) int {
 2     high := len(nums) - 1
 3     var low, middle, middleValue int
 4     for low <= high { //退出条件是小于等于
 5         middle = low + (high - low) / 2 //防止出现越界
 6         middleValue = nums[middle]
 7         if middleValue == target {
 8             return middle
 9         } else if middleValue > target {
10             high = middle - 1
11         } else {
12             low = middle + 1
13         }
14     }
15     return -1
16 }

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。你的算法时间复杂度必须是 O(log n) 级别。
如果数组中不存在目标值，返回 [-1, -1]。

示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]

示例 2:
输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

 1 class Solution {
 2 
 3     /**
 4      * @param Integer[] $nums
 5      * @param Integer $target
 6      * @return Integer[]
 7      */
 8     function searchRange($nums, $target) {
 9         $len = count($nums);
10         $r = $len;
11         $l = 0;
12         $middle = 0;
13         $found = false;
14         while ($l <= $r && !$found) {
15             $middle = ceil($l+($r-$l)/2); //向上取整，PHP 不是整除时会发生类型转换
16             switch (true) {
17                 case $nums[$middle] > $target:
18                     $r = $middle - 1; break;
19                 case $nums[$middle] < $target:
20                     $l = $middle + 1; break;
21                 default : $found = true; break;
22             }
23         }
24         if ($nums[$middle] !== $target) {
25             return [-1, -1];
26         } else {
27             for ($l=$middle; $l>0&&$nums[$l-1]==$target;){
28                 $l--;
29             }
30             for ($r=$middle; $r<$len-1&&$nums[$r+1]==$target;){
31                 $r++;
32             }
33             return [$l, $r];
34         }
35     }
36 }