34. 在排序数组中查找元素的第一个和最后一个位置

题意：

解题思路：

思路：
1. 通过二分查找找到target后，继续左右移动，直到遇到边界停止
2. 最后返回目标值的最小跟最大边界值

PHP代码实现：

class Solution {
    function findFirstAndLastPosition($nums, $target) {
        if ($nums == null) return [-1, -1];
        $start = -1;
        $end = -1;
        $n = count($nums);
        for ($i = 0; $i < $n; $i++) {
            if ($nums[$i] == $target) {
                $start = $i;
                break;
            }
        }
        for ($j = $n - 1; $j >= 0; $j--) {
            if ($nums[$j] == $target) {
                $end = $j;
                break;
            }
        }
        return [$start, $end];
    } 
    function searchRange($nums, $target) {
        if ($nums == null) return [-1, -1];
        $left = 0;
        $right = count($nums) - 1;
        $result = [-1, -1];
        while ($left <= $right) {
            $mid = $left + floor(($right - $left) / 2);
            if ($nums[$mid] == $target) {
                while ($mid >= $left && $nums[$mid] == $target) {
                    $mid--;
                }
                $first = $mid + 1;
                $mid = $left + floor(($right - $left) / 2);
                while ($mid <= $right && $nums[$mid] == $target) {
                    $mid++;
                }
                $second = $mid - 1;
                $result = [$first, $second];
                break;
            } else if ($nums[$mid] > $target) {
                $right = $mid - 1;
            } else {
                $left = $mid + 1;
            }
        }
        return $result;
    }
    function searchRange1($nums, $target) {
        if ($nums == null) return [-1, -1];
        $left = $this->leftBound($nums, $target); 
        $right = $this->rightBound($nums, $target);
        return [$left, $right];
    }
    function leftBound($nums, $target) {
        $left = 0;
        $right = count($nums);
        while ($left < $right) {
            $mid = $left + floor(($right - $left) / 2);
            if ($nums[$mid] == $target) {
                $right = $mid;
            } else if ($nums[$mid] < $target) {
                $left = $mid + 1;
            } else if ($nums[$mid] > $targer) {
                $right = $mid - 1;
            }
            if ($left == count($nums)) return -1;
        }
        return $nums[$left] == $target ? $left : -1;
    }
    function rightBound($nums, $target) {
        $left = 0;
        $right = count($nums);
        while ($left < $right) {
            $mid = $left + floor(($right - $left) / 2);
            if ($nums[$mid] == $target) {
                $left = $mid + 1;
            } else if ($nums[$mid] < $target) {
                $left = $mid + 1;
            } else if ($nums[$mid] > $targer) {
                $right = $mid;
            }
        }
        return $nums[$left - 1] == $target ? ($left - 1) : -1;
    }
    function searchRange2($nums, $target) {
        $l = 0;
        $r = count($nums) - 1; 
        while ($l < $r) {
            $mid = $l + floor(($r - $l) / 2);
            if ($nums[$mid] >= $target) $r = $mid;
            else $l = $mid + 1;
        }
        if ($nums[$l] != $target) {
            return [-1, -1];
        } else {
            $l = 0;
            $r = count($nums) - 1; 
            while ($l < $r) {
                $mid = $l + $r + 1 >> 1;
                if ($nums[$mid] <= $target) $l = $mid;
                else $r = $mid - 1;
            }
            return [$l, $l];
        }
        return [-1, -1];
    }
}

GO代码实现：

func searchRange(nums []int, target int) []int {
    l := len(nums)
    if l == 0 {
        return []int{-1, -1}
    }
    left, right := 0, l-1
    a, b := -1, -1
    for left <= right {
        mid := (left + right) / 2
        if nums[mid] == target {
            a, b = mid, mid
            for a > left && nums[a-1] == target {
                a--
            }
            for b < right && nums[b+1] == target {
                b++
            }
            break
        }
        if nums[mid] > target {
            right = mid - 1
        }
        if nums[mid] < target {
            left = mid + 1
        }
    }
    return []int{a, b}
}