#
##
****//-1
- 1start=0end=len-1
- 2start + 1 < end
- 3A[mid] == target
- 4A[start]A[end] ? target
O(logn)
[binary-search](https://leetcode-cn.com/problems/binary-search/)
> n nums target nums target -1
```go
//
func search(nums []int, target int) int {
// 1startend
start := 0
end := len(nums) - 1
// 2for
for start+1 < end {
mid := start + (end-start)/2
// 3a[mid]target
if nums[mid] == target {
end = mid
} else if nums[mid] < target {
start = mid
} else if nums[mid] > target {
end = mid
}
}
// 4
if nums[start] == target {
return start
}
if nums[end] == target {
return end
}
return -1
}
```
#3 /
#3 [](https://leetcode-cn.com/explore/learn/card/binary-search/212/template-analysis/847/)
#1
```go
//
func search(nums []int, target int) int {
start := 0
end := len(nums) - 1
for start target {
end = mid-1
}
}
// start target
// B+return start
// node:=node.Children[start]
return -1
}
```
##
### [search-for-range](https://www.lintcode.com/problem/search-for-a-range/description)
> n target
> `[-1, -1]`
target target
```go
func searchRange (A []int, target int) []int {
if len(A) == 0 {
return []int{-1, -1}
}
result := make([]int, 2)
start := 0
end := len(A) - 1
for start+1 < end {
mid := start + (end-start)/2
if A[mid] > target {
end = mid
} else if A[mid] < target {
start = mid
} else {
//
end = mid
}
}
//
if A[start] == target {
result[0] = start
} else if A[end] == target {
result[0] = end
} else {
result[0] = -1
result[1] = -1
return result
}
start = 0
end = len(A) - 1
for start+1 < end {
mid := start + (end-start)/2
if A[mid] > target {
end = mid
} else if A[mid] < target {
start = mid
} else {
//
start = mid
}
}
//
if A[end] == target {
result[1] = end
} else if A[start] == target {
result[1] = start
} else {
result[0] = -1
result[1] = -1
return result
}
return result
}
```
### [search-insert-position](https://leetcode-cn.com/problems/search-insert-position/)
>
```go
func searchInsert(nums []int, target int) int {
// >= target
start := 0
end := len(nums) - 1
for start+1 < end {
mid := start + (end-start)/2
if nums[mid] == target {
//
start = mid
} else if nums[mid] > target {
end = mid
} else {
start = mid
}
}
if nums[start] >= target {
return start
} else if nums[end] >= target {
return end
} else if nums[end] < target { //
return end + 1
}
return 0
}
```
### [search-a-2d-matrix](https://leetcode-cn.com/problems/search-a-2d-matrix/)
> m x n
>
> -
> -
```go
func searchMatrix(matrix [][]int, target int) bool {
// 21
if len(matrix) == 0 || len(matrix[0]) == 0 {
return false
}
row := len(matrix)
col := len(matrix[0])
start := 0
end := row*col - 1
for start+1 < end {
mid := start + (end-start)/2
// 2
val := matrix[mid/col][mid%col]
if val > target {
end = mid
} else if val < target {
start = mid
} else {
return true
}
}
if matrix[start/col][start%col] == target || matrix[end/col][end%col] == target{
return true
}
return false
}
```
### [first-bad-version](https://leetcode-cn.com/problems/first-bad-version/)
> n [1, 2, ..., n]
> bool isBadVersion(version) version API
```go
func firstBadVersion(n int) int {
//
start := 0
end := n
for start+1 < end {
mid := start + (end - start)/2
if isBadVersion(mid) {
end = mid
} else if isBadVersion(mid) == false {
start = mid
}
}
if isBadVersion(start) {
return start
}
return end
}
```
### [find-minimum-in-rotated-sorted-array](https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/)
> ( [0,1,2,4,5,6,7] [4,5,6,7,0,1,2])
>
```go
func findMin(nums []int) int {
// / / targetstartend
if len(nums) == 0 {
return -1
}
start := 0
end := len(nums) - 1
for start+1 < end {
mid := start + (end-start)/2
// target
if nums[mid] nums[end] {
return nums[end]
}
return nums[start]
}
```
### [find-minimum-in-rotated-sorted-array-ii](https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii/)
>
> ( [0,1,2,4,5,6,7] [4,5,6,7,0,1,2])
> ()
```go
func findMin(nums []int) int {
// midend
if len(nums) == 0 {
return -1
}
start := 0
end := len(nums) - 1
for start+1 < end {
//
for start < end && nums[end] == nums[end-1] {
end--
}
for start < end && nums[start] == nums[start+1] {
start++
}
mid := start + (end-start)/2
//
if nums[mid] nums[end] {
return nums[end]
}
return nums[start]
}
```
### [search-in-rotated-sorted-array](https://leetcode-cn.com/problems/search-in-rotated-sorted-array/)
>
> ( [0,1,2,4,5,6,7] [4,5,6,7,0,1,2])
> -1
>
```go
func search(nums []int, target int) int {
// / /
if len(nums) == 0 {
return -1
}
start := 0
end := len(nums) - 1
for start+1 < end {
mid := start + (end-start)/2
//
if nums[mid] == target {
return mid
}
//
if nums[start] < nums[mid] {
if nums[start] = target && nums[mid]
### [search-in-rotated-sorted-array-ii](https://leetcode-cn.com/problems/search-in-rotated-sorted-array-ii/)
>
> ( [0,0,1,2,2,5,6] [2,5,6,0,0,1,2])
> true false()
```go
func search(nums []int, target int) bool {
// / /
if len(nums) == 0 {
return false
}
start := 0
end := len(nums) - 1
for start+1 < end {
//
for start < end && nums[start] == nums[start+1] {
start++
}
for start < end && nums[end] == nums[end-1] {
end--
}
mid := start + (end-start)/2
//
if nums[mid] == target {
return true
}
//
if nums[start] < nums[mid] {
if nums[start] = target && nums[mid]