題目
Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.
You must write an algorithm with O(log n) runtime complexity.
- 題意: 在nums陣列中找出等於target的index值 ，並且時間複雜度須為O(log n)
解法
- 題目要求: 時間複雜度為 O(log n) ，所以可以使用Binary Search 方法來找出index
func search(nums []int, target int) int {
start := 0
end := len(nums) - 1
for start <= end {
mid := start + (end-start)/2
if nums[mid] == target {
return mid
} else if nums[mid] > target {
end = mid - 1
} else {
start = mid + 1
}
}
return -1
}
- 加些測試，看看結果是不是如預期
import (
"github.com/stretchr/testify/assert"
"testing"
)
func Test_search_case1(t *testing.T) {
assert.Equal(t, 4, search([]int{-1, 0, 3, 5, 9, 12}, 9))
}
func Test_search_case2(t *testing.T) {
assert.Equal(t, -1, search([]int{-1, 0, 3, 5, 9, 12}, 2))
}