Contents

# Array

## 題目 :

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.

You must write an algorithm with O(log n) runtime complexity.

### Example :

Note

Input: nums = [5,7,7,8,8,10], target = 8 Output: [3,4]

Input: nums = [5,7,7,8,8,10], target = 6 Output: [-1,-1]

### 以下是我自己的解法 - O(lgn)

Runtime: 4 ms, faster than 99.23% of Go online submissions for Find First and Last Position of Element in Sorted Array.

#### 解題思路 :

• 找到第一個值等於target的elements
• 找到最後一個值等於target的elements
• 找到第一個大於等於target的elements
• 找到最後一個值小於等於target的elements

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 `````` `````` func searchRange(nums []int, target int) []int { return []int{searchFirstEqualElement(nums, target) , searchLastEqualElement(nums, target)} } func searchFirstEqualElement(nums []int, target int) int { low, high := 0, len(nums)-1 for low <= high { mid := low + ((high-low) >> 1) if nums[mid] > target { high = mid - 1 }else if nums[mid] < target { low = mid + 1 }else { if mid == 0 || nums[mid-1] != target { return mid } high = mid -1 } } return -1 } func searchLastEqualElement(nums []int, target int) int { low, high := 0, len(nums)-1 for low <= high { mid := low + ((high-low) >> 1) if nums[mid] > target { high = mid - 1 }else if nums[mid] < target { low = mid + 1 }else { if mid == (len(nums)-1) || nums[mid+1] != target { return mid } low = mid + 1 } } return -1 } ``````