代码随想录——二分查找(一)

模版

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
}