lt33 搜索旋转数组
找到target下标，不在则返回-1
func search(nums []int, target int) int {
//边界判断
if len(nums)==0{
return -1
}
l:=0
r:=len(nums)-1
for l<=r{
mid:=l+(r-l)/2
if nums[mid]==target{
return mid
}
//分为左边有序和右边有序
if nums[l]<=nums[mid]{//左边有序
//在左边和不再左边
if nums[l]<=target&&target<=nums[mid]{
r = mid-1
}else{
l = mid+1
}
}else{
//在右边和不再右边
if nums[mid]<=target&&target<=nums[r]{
l = mid+1
}else{
r = mid-1
}
}
}
//都不是反-1
return -1
}
lt34 排序数组寻找第一个和最后一个位置
func searchRange(nums []int, target int) []int {
res:=[]int{-1,-1}
if len(nums)==0{
return res
}
l:=0
r:=len(nums)-1
for l<=r{
mid:=l+(r-l)/2
if nums[mid]>target{
r = mid-1
}else if nums[mid]<target{
l = mid+1
}else{
start:=mid
end:=mid
for start>0&&nums[start-1]==target{
start--
}
for end<len(nums)-1&&nums[end+1]==target{
end++
}
res[0] = start
res[1] = end
return res
}
}
return res
}
lt 153旋转数组搜索最小值I
数组元素不重复
func findMin(nums []int) int {
if len(nums)==0{
return 0
}
//判断中间和最右边的关系
l:=0
r:=len(nums)-1
for l<r{
mid:=l+(r-l)/2
if nums[mid]>nums[r]{
l = mid+1
}else{
r = mid
}
}
return nums[l]
}
lt 154旋转数组搜索最小值II
数组包含重复元素
增加判断重复元素的步骤
func findMin(nums []int) int {
if len(nums)==0{
return 0
}
//判断中间和最右边的关系
l:=0
r:=len(nums)-1
for l<r{
//增加判断重复元素
for l<r&&nums[l]==nums[l+1]{
l++
}
for l<r&&nums[r]==nums[r-1]{
r--
}
mid:=l+(r-l)/2
if nums[mid]>nums[r]{
l = mid+1
}else{
r = mid
}
}
return nums[l]
}