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

题目：

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

解题：

挨着比较相等就返回第一个和最后一个下标

代码：

func searchRange(nums []int, target int) []int {
    start, end := -1, -1
    for i, v := range nums {
        if v == target {
            if start == -1 {
                start = i
            }
            end = i
        }
    }
    return []int{start, end}
}

官方解答： 

// 二分查找
// 这个是用了内置函数的，感觉跟偷鸡一样一样的
func searchRange(nums []int, target int) []int {
    leftmost := sort.SearchInts(nums, target)
    if leftmost == len(nums) || nums[leftmost] != target {
        return []int{-1, -1}
    }
    rightmost := sort.SearchInts(nums, target + 1) - 1
    return []int{leftmost, rightmost}
}
// 这个是从Java翻译过来的
func searchRange(nums []int, target int) []int {
    leftIdx := binarySearch(nums, target, true)
    rightIdx := binarySearch(nums, target, false) - 1
    if leftIdx <= rightIdx && rightIdx < len(nums) && nums[leftIdx] == target && nums[rightIdx] == target {
        return []int{leftIdx, rightIdx}
    }
    return []int{-1, -1}
}

func binarySearch(nums []int, target int, lower bool) int {
    left, right, ans := 0, len(nums)-1, len(nums)
    for left <= right {
        mid := (left + right) / 2
        if nums[mid] > target || (lower && nums[mid] >= target) {
            right = mid - 1
            ans = mid
        } else {
            left = mid + 1
        }
    }
    return ans
}

自己的解法时间复杂度只有 O(n)