funcmySqrt(x int)int { lx := int64(x) var left int64 = 0 var right int64 = lx/2 + 1 for left < right { mid := left + (right-left)/2 if mid*mid < lx { left = mid + 1 //向下取整的，所以需要额外判断或者取右中位数 if left*left > lx { returnint(mid) } } else { right = mid } } returnint(left) }
还有一种比较好的解法，更加贴合模板
//这个其实更能体现模板的好处 funcmySqrt(x int)int { lx := int64(x) var left int64 = 0 var right int64 = lx/2 + 1 for left < right { mid := left + (right-left)/2 + 1 //大于lx的一定不是res可以排除，但是小于的不一定不是，题目是向下取整的 if mid*mid > lx { right = mid - 1 } else { left = mid } } returnint(left) }
funcfindMin(nums []int)int { var n = len(nums) var left, right = 0, n - 1 var res = right//对nums[n-1]就是最小值做兜底 for left <= right { mid := left + (right-left)/2 if nums[mid] < nums[n-1] { res = mid right = mid - 1 } else { left = mid + 1 } } return nums[res] }
同理也可以和左边界比较，最小值一定是小于等于nums[0]的
funcfindMin(nums []int)int { var n = len(nums) var left, right = 0, n - 1 var res = left //对nums[0]就是最小值做兜底 for left <= right { mid := left + (right-left)/2 if nums[mid] < nums[0] { res = mid right = mid - 1 } else { left = mid + 1 } } return nums[res] }
# update: 2020/4/8 classSolution: deffindMin(self, nums: List[int]) -> int: left, right = 0, len(nums)-1 res = 0 while right >= 0and nums[right] == nums[0]: right -= 1 nr = right while left <= right: mid = left + (right - left)//2 # 和nr比，不能和0比，可能会有0 1 2这样的 if nums[mid] > nums[nr]: left = mid + 1 else: res = mid right = mid - 1 return nums[res]
classSolution: defsearch(self, nums: List[int], target: int) -> bool: left, right = 0, len(nums)-1 res = 0 # 尾部去重，方便确定target和mid所在区间 while right >= 0and nums[right] == nums[0]: right -= 1 while left <= right: mid = left + (right-left)//2 v = nums[mid] if (nums[mid] < nums[0]) == (target < nums[0]) else float("inf") if nums[mid] < nums[0] else float("-inf") if v <= target: res = mid left = mid + 1 else: right = mid - 1 returnTrueif nums[res] == target elseFalse
funcfindInMountainArray(target int, mountainArr *MountainArray)int { n := mountainArr.length() //寻找山顶 left := 0 right := n - 1 for left < right { mid := left + (right-left)/2 //mid+1肯定不会越界 if mountainArr.get(mid) < mountainArr.get(mid+1) { left = mid + 1 } else { right = mid } } res := -1 res = binarySearchUp(mountainArr, target, 0, left) if res == -1 { res = binarySearchDown(mountainArr, target, left, n-1) } return res }
funcbinarySearchUp(mountainArr *MountainArray, target, left, right int)int { for left < right { mid := left + (right-left)/2 if mountainArr.get(mid) < target { left = mid + 1 } else { right = mid } } if mountainArr.get(left) == target { return left } return-1 }
funcbinarySearchDown(mountainArr *MountainArray, target, left, right int)int { for left < right { mid := left + (right-left)/2 if mountainArr.get(mid) > target { left = mid + 1 } else { right = mid } } if mountainArr.get(left) == target { return left } return-1 }
这两个二分是可以合并的，懒得合了（太懒了吧你也😅）
UPDATE: 2020.7.14
自定义函数传递，简化代码
funcfindInMountainArray(target int, mA *MountainArray)int { var n = mA.length() var left = 0 var right = n-1 var maxIdx = right for left <= right{ mid := left + (right-left)/2 //左中，所以mid+1不会越界 if mA.get(mid) > mA.get(mid+1){ maxIdx = mid right = mid - 1 }else{ left = mid + 1 } } lr := search(mA, target, 0, maxIdx, func(i int, j int)bool{ return i <= j }) if lr != -1{ return lr } return search(mA, target, maxIdx+1, n-1, func(i int, j int)bool{ return i >= j }) }
funcsearch(mA *MountainArray, target int, left int, right int, less func(int, int)bool) int { var res = left for left <= right{ mid := left + (right-left)/2 if less(mA.get(mid), target){ res = mid left = mid + 1 }else{ right = mid - 1 } } if mA.get(res) != target{ return-1 } return res }
funccountNegatives(grid [][]int)int { iflen(grid) <= 0 { return0 } var m, n = len(grid), len(grid[0]) var count = 0 var i, j = m-1, 0 for i >= 0 && j < n { if grid[i][j] < 0 { count += n - j i-- }else{ j++ } } return count; }
解法二
O(mlogn)解法
//O(mlogn) 只利用了行逆序的条件 funccountNegatives(grid [][]int)int { iflen(grid) <= 0 { return0 } var count = 0 var m = len(grid) var n = len(grid[0]) for i := 0; i < m; i++ { count += (n - search(grid[i])) } return count }
funcsearch(nums []int)int { var left = 0 var right = len(nums)-1 var res = right+1 for left <= right { mid := left + (right-left)/2 if nums[mid] < 0 { res = mid right = mid - 1 }else{ left = mid + 1 } } return res }
funcisPerfectSquare(num int)bool { var left = 0 var right = num var res = num + 1 for left <= right { mid := left + (right-left)/2 if mid*mid >= num { res = mid right = mid - 1 } else { left = mid + 1 } } return res*res == num }
解法二
完全平方数的性质
//完全平方数性质 n^2 = 1 + 3 + 5 +...+2n+1 (前n个奇数的和) //所以只需要判断num能不能被奇数减成0就行了 funcisPerfectSquare(num int)bool { var i = 1 for num > 0 { num -= i i += 2 } return num == 0 }
funcfindRadius(houses []int, heaters []int)int { //边界处理 heaters = append(heaters, math.MaxInt32) heaters = append(heaters, math.MinInt32) sort.Ints(heaters) var Min = func(a, b int)int { if a < b {return a}; return b} var Max = func(a, b int)int { if a < b {return b}; return a} var res = 0 for _, h := range houses{ left := search(heaters, h) res = Max(res, Min(h-heaters[left], heaters[left+1]-h)) } return res } //target左边最近的一个 funcsearch(heaters []int, target int)int { var left, right = 0, len(heaters)-1 var res = left //左边没有供暖器 for left <= right { mid := left + (right-left)/2 if heaters[mid] <= target{ res = mid left = mid + 1 }else{ right = mid - 1 } } return res }
另一种写法，不额外处理边界，也是一开始的写法
funcfindRadius(houses []int, heaters []int)int { sort.Ints(heaters) var n = len(heaters) var Min = func(a, b int)int { if a < b {return a}; return b} var Max = func(a, b int)int { if a < b {return b}; return a} var res = 0 for _, h := range houses{ left := search(heaters, h) if left == -1{ //全部大于hourse,取最小的那个 res = Max(res, heaters[0]-h) }elseif left+1 < n{ res = Max(res, Min(h-heaters[left], heaters[left+1]-h)) }else{ res = Max(res, h-heaters[left]) } } return res }
//target左边最近的一个 funcsearch(heaters []int, target int)int { var left, right = 0, len(heaters)-1 var res = -1//左边没有供暖器 for left <= right { mid := left + (right-left)/2 if heaters[mid] <= target{ res = mid left = mid + 1 }else{ right = mid - 1 } } return res }
funcfindRadius(houses []int, heaters []int)int { heaters = append(heaters, math.MaxInt32) heaters = append(heaters, math.MinInt32) sort.Ints(heaters) sort.Ints(houses) var n = len(heaters) var Min = func(a, b int)int { if a < b {return a}; return b} var Max = func(a, b int)int { if a < b {return b}; return a} var res = 0 var left = 0 for _, h := range houses { for left < n && heaters[left] < h { left++ } res = Max(res, Min(heaters[left]-h, h-heaters[left-1])) } return res }
时间复杂度细看的话应该是 O(NlogN + MlogM + N + M)（M，N分别代表houses和heaters的长度），差别不大，不过很明显双指针的好写很多
publicintsmallestDivisor(int[] nums, int threshold){ int left=1,right=1000000; while(left<right){ int mid=left+(right-left)/2; int sum=0; for (int i=0;i<nums.length;i++) { sum+=(nums[i]+mid-1)/mid; //向上取整 } if (sum>threshold) { left=mid+1; }else{ right=mid; } } return left; }
//最小值最大 publicintsolve(int n, int k, int[] a){ int left = 0; int right = 0; for (int i = 0; i < a.length; i++) { left = Math.min(left, a[i]); right += a[i]; } int res = 0; while (left <= right) { int mid = left + (right-left)/2; if (check(mid, a, k)) { res = mid; left = mid + 1; }else { right = mid - 1; } } return res; }
//分为k组能否保证每组都大于等于mid（如果可以说明还可以更大） publicbooleancheck(int mid, int[] a, int k){ int sum = 0; int count = 0; for (int i = 0; i < a.length; i++) { sum += a[i]; if (sum >= mid) { sum = 0; count++; } } return count >= k; }
publicintminDays(int[] bloomDay, int m, int k){ int n=bloomDay.length; if(m*k>n) return -1; //花园的花不够 //直接写就完事了，这里数据范围只到1e9，log(1e9)很小的，只有30左右 int left=1,right=(int)1e9; int res=right+1; while(left<=right){ int mid=left+(right-left)/2; if(check(bloomDay,m,k,mid)){ res=mid; right=mid-1; }else{ left=mid+1; } } return res; }
publicintminDays(int[] bloomDay, int m, int k){ int n=bloomDay.length; if(m*k>n) return -1; //花园的花不够 //直接写就完事了，这里数据范围只到1e9，log(1e9)很小的，只有30左右 int left=1,right=(int)1e9; int res=right+1; while(left<=right){ int mid=left+(right-left)/2; if(check(bloomDay,m,k,mid)){ res=mid; right=mid-1; }else{ left=mid+1; } } return res; }
publicbooleancheck(int[] bloomDay,int m,int k,int day){ int i=0; int count=0; int temp=0; //相邻的开花数量 for(int d:bloomDay){ if(d<=day){ //花开了(md，这个if写反两次) temp++; }else{ temp=0; } if(temp==k){ temp=0; count++; } } return count>=m; }
publicintkthSmallest(int[][] matrix, int k){ int n = matrix.length; int left = matrix[0][0]; int right = matrix[n-1][n-1]; int res = left; while(left <= right){ int mid = left + (right - left)/2; //注意这个地方，很关键，核心就是这个等于号的位置，在小于等于mid的数量==k的时候二分的区间应该如何移动 //其实举个例子就懂了，假设k=2，对于结果应该是5，但是我们现在mid=8 //这里8和5在矩阵中小于等于它们的数量是相同的，这个时候很明显应该缩短right去逼近5 //所以我们应该在二分的大于等于区间记录答案，并且缩短right if (check(matrix, mid) >= k){ res = mid; right = mid - 1; }else{ left = mid + 1; } } return res; }
//检查数组中小于等于mid的个数 publicintcheck(int[][] matrix, int mid){ int row = matrix.length-1, column = 0; int count = 0; int lastRow = 0; while(row >= 0){ while (column < matrix[0].length && matrix[row][column] <= mid){ column++; lastRow++; } count += lastRow; row--; } return count; }
//二分答案 publicintarrangeCoins(int n){ int left = 1; int right = n; int res = 0; while(left <= right){ long mid = left + (right - left)/2; long sum = (1 + mid) * mid / 2; if(sum <= n){ res = (int)mid; left = (int)mid + 1; }else{ right = (int)mid - 1; } } return res; }
publicintcalculateMinimumHP(int[][] dungeon){ int left = 0; int right = Integer.MAX_VALUE; int res = 0; while(left <= right){ int mid = left + (right-left)/2; if(check(dungeon, mid)){ res = mid; right = mid - 1; }else{ left = mid + 1; } } return res; }
publicbooleancheck(int[][] dungeon, int live){ int m = dungeon.length; int n = dungeon[0].length; int INF = Integer.MIN_VALUE; //live的血量从左上到dungeon[i][j]的剩余最多血量 int[][] dp = newint[m+1][n+1]; //地牢外围加上INF的围墙，简化逻辑 Arrays.fill(dp[0], INF); dp[0][1] = live; for(int i = 1; i <= m; i++){ dp[i][0] = INF; for(int j = 1; j <= n; j++){ if(dp[i-1][j] <= 0 && dp[i][j-1] <=0 ){ dp[i][j] = INF; //无法到达这里 }else{ dp[i][j] = dungeon[i-1][j-1] + Math.max(dp[i][j-1], dp[i-1][j]); } } } return dp[m][n] > 0; }
publicdoubleminmaxGasDist(int[] stations, int k){ // Write your code here double left = 0; double right = 1e8+1; double res = right; //for (int i = 0; i <= 100; i++){ while (right-left >= 1e-6){ double mid = left+(right-left)/2; if (check(stations, k, mid)) { res = mid; right = mid; }else{ left = mid; } } return res; }
publicbooleancheck(int[] stations, int k, double D){ int count = 0; for (int i = 1; i < stations.length; i++) { count += (stations[i]-stations[i-1]) / D; } return count <= k; }
publicintmaxDistance(int[] position, int m){ Arrays.sort(position); int left = 1; int right = (int)1e9+1; int res = 1; while (left <= right) { int mid = left + (right-left)/2; if (check(position, m, mid)) { res = mid; left = mid + 1; }else{ right = mid - 1; } } return res; } //1 1000 2000 3000 m=3 //验证在距离至少为force的情况下能否放下所有的球，然后增大force逼近答案 //所以check验证成功的不一定是合法的答案，但是最终一定会到达real ans //类似【378. 有序矩阵中第K小的元素】这道题 publicbooleancheck(int[] position, int m, int force){ int last = position[0]; m--; for (int i = 1; i < position.length; i++) { if (position[i]-last < force) { continue; } last = position[i]; m--; if (m==0) returntrue; } returnfalse; }
