代码随想录——二分查找(一)
模版
func BinarySearch(nums *int,target int){l,r:=0,len(nums)-1for l<=r{mid:=l+(r-l)/2if nums[mid]==target{return mid}else if nums[mid]<target{l=mid+1}else{r=mid-1}}return -1
}
特点
- 查找条件可以在不与元素的两侧进行比较的情况下确定（或使用它周围的特定元素）。
- 不需要后处理，因为每一步中，你都在检查是否找到了元素。如果到达末尾，则知道未找到该元素。
例题
一.Leetcode69——x的平方根
解题代码：
func mySqrt(x int) int {if x==0{return x}l,r:=0,xans:=-1for l<=r{mid:=l+(r-l)/2if mid*mid>x{r=mid-1}else{ans=midl=mid+1}}return ans
}
二.猜数字大小
func guessNumber(n int) int {l,r:=1,nfor l<=r{mid:=(r-l)/2+lif guess(mid)==0{return mid}else if guess(mid)==-1{r=mid-1}else{l=mid+1}}return -1
}
三.搜索旋转排序数组
解析：
这道题要求的时间复杂度是O(logn),这注定我们不能遍历这一个数组，所以我们不能暴力解题，我们可以观察这个旋转数组，由于它已经经过了一次排序，所以它虽然不是全局有序但是至少局部有序，所以我们可以尝试稍微修改二分查找的条件来适应这种情况，因为排过序所以其实它还是可以分为两个局部有序的子数组，所以我们可以根据这个对数组进行处理，如下图：
示例代码如下：
func search(nums []int, target int) int {n:=len(nums)if n==0{return -1}if n==1{if target==nums[0]{return 0}else{return -1}}l,r:=0,n-1for l<=r{mid:=(r-l)/2+lif target==nums[mid]{return mid}if nums[l]<=nums[mid]{if nums[l]<=target && target<nums[mid]{r=mid-1}else{l=mid+1}}else if nums[r]>nums[mid]{if nums[r]>=target && target>nums[mid]{l=mid+1}else{r=mid-1}}}return -1
}