题目描述:
给定一个按照升序排列的整数数组 nums
,和一个目标值 target
。
找出给定目标值在数组中的开始位置和结束位置,如果数组中不存在目标值 target
,返回 [-1, -1]
。
设计并实现时间复杂度为 O(log(n))
的算法解决此问题。
编写语言Swift
func seek(numArray: [Int], target: Int) -> (Int, Int) { if numArray.count == 0 { return (-1, -1) } var min = 0, max = numArray.count - 1, first = -1, last = -1 while min <= max { let mid = (max - min)/2 + min if numArray[mid] >= target { first = mid max = mid - 1 } else { min = mid + 1 } } // 到此可以找到最先出现的位置, 可以以最先出现的位置为起始点开始计算最后出现的位置 min = first max = numArray.count - 1 while min <= max { let mid = (max - min)/2 + min if numArray[mid] <= target { last = mid min = mid + 1 } else { max = mid - 1 } } if numArray[first] != target { first = -1 } return (first, last) }