一分为二,化繁为简
思路
预处理–数组有序,不是有序则 先排序
二分查找–将数组一分为二
后处理–剩余一半数组中查找可行的范围
三个模板
模板一 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 int binarySerach1 (int [] nums, int target) { if (nums == null || nums.length == 0 ) { return -1 ; } int left = 0 , right = nums.length - 1 ; while (left <= right) { int mid = left + (right - left) / 2 ; if (nums[mid] == target) { return mid; } else if (nums[mid] > target) { right = mid - 1 ; } else { left = mid + 1 ; } } return -1 ; }
X的平方根 题目 给你一个非负整数 x ,计算并返回 x 的 算术平方根 。 由于返回类型是整数,结果只保留 整数部分 ,小数部分将被 舍去 。 注意:不允许使用任何内置指数函数和算符,例如 pow(x, 0.5) 或者 x ** 0.5 。
解题思路 找x的平方根,其实就是找一个使n * n <= x 成立的最大的 n。
代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 int MySqrt1 (int x) { int left = 0 , right = x; int ans = -1 ; while (left <= right){ int mid = (right - left) / 2 + left; if (mid * mid <= x){ ans = mid; left = mid + 1 ; } else { right = mid - 1 ; } } return ans; }
模板二 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 int binarySearch2 (int [] nums, int target) { if (nums == null || nums.length == 0 ) return -1 ; int left = 0 , right = nums.length; while (left < right) { int mid = left + (right - left) / 2 ; if (nums[mid] == target) { return mid; } else if (nums[mid] < target) { left = mid + 1 ; } else { right = mid; } } if (left != nums.length && nums[left] == target) return left; return -1 ; }
X的平方根 [left,right)解法 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 int MaSqrt2 (int x) { int left = 0 , right = x + 1 ; int ans = -1 ; while (l < r){ int mid = (right - left) / 2 + left; if (mid * mid <= x){ ans = mid; left = mid + 1 ; } else { right = mid; } } return ans; }
模板三 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 int binarySearch3 (int [] nums, int target) { if (nums == null || nums.length == 0 ) return -1 ; int left = 0 , right = nums.length - 1 ; while (left + 1 < right) { int mid = left + (right - left) / 2 ; if (nums[mid] == target) { return mid; } else if (nums[mid] < target) { left = mid; } else { right = mid; } } if (nums[left] == target) return left; if (nums[right] == target) return right; return -1 ; }
X的平方根 (left,right)解法 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 int MySqrt3 (int x) { int left = -1 , right = x + 1 ; int ans = -1 ; while (left + 1 < right){ int mid = (right - left) / 2 + left; if (mid * mid <= x){ ans = mid; left = mid; } else { right = mid; } } return ans; }
区别
初始边界left和right不同
while()
内判断条件不同
left和right后处理的不同
首先明白我们二分搜索的区间是怎么划分的。
初始化边界
如果是[left,right],那么left = 0,right = nums.size() - 1
。这样刚好包含nums数组全部数组,如果right = nums.size()
,则多包含了一个数组外的数
如果是[left,right),那么left = 0,right = nums.size()
。跟[]不同,right = nums.size()
时才能刚好把数组包含,如果right = nums.size() - 1,则会少一个右边界元素。
如果使(left,right),那么left = -1,right = nums.size()
。
while内判断条件 不断将区间一分为二,当出现不合法的区间时中断循环。
[left,right],只需要判断条件合法即可,left <= right
情况可能出现,如果选择left < right
则少了一个循环
[left,right),不可能出现left = right
,因此left< right
即可决定循环是否中止
(left,right),left 也不能使用left 与 right是否相等来中止循环,当left - 1 = right
(此情况不存在)时就需要中止循环
left right后处理 根据区间类型看mid是否在二分后的区间内来决定后处理。 为方便处理,改为寻找与target相等的下标(为方便表述,mid代表下标为mid的数组值)
[left,right]
mid < target
,如果left = mid
,划分后的区间仍然包含已经进行判断过的mid,因此应该为mid + 1。
mid > target
,如果right = mid
,划分后的区间仍然包含…
mid = target
,找到结果,返回
[left,right)
mid < target
,left = mid
即可满足划分后的区间不包含判断过的mid(右开)
mid > target
,left = mid + 1
,同左闭
mid = target
,不会有这种情景,在left - 1 = right循环就中止了
(left,right)
mid < target
,left = mid
mid > target
,right = mid
mid = target
,不会有这种情景,在left - 1 = right循环就中止了
总结 对于不同的问题,以上三种模板其实都可以使用,不过是实现方法的不同而已。对于不同的问题选择不同的模板可以有助于代码的理解与实现。
例题 搜索插入的位置 题目 给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution {public : int searchInsert (vector<int >& nums, int target) { int l = 0 , r = nums.size () - 1 ; while (l <= r){ int mid = (r - l) / 2 + l; if (nums[mid] < target){ l = mid + 1 ; } else { r = mid - 1 ; } } return l; } };
这个代码是抄的别人的,自己写的巨麻烦😫。
总结 该题相当于找最后一个小于target
的下一个下标(或者说第一个大于或等于target
的数组值的下标),随着循环进行,l代表的是最后一个小于target
的下一个下标,而r代表的是第一个大于等于target
的数组值的上一个下标 ,我们要返回的是最后一个小于target
的下一个下标,即l。
对于题目要求的结果,我们要分析并总结出其对应的编程语言,并理解left,right
对应的是什么。
在排序数组中查找元素的第一个和最后一个位置 题目 给你一个按照非递减顺序排列的整数数组 nums
,和一个目标值 target
。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target
,返回 [-1, -1]
。
思路一 根据二分特性,随着循环进行,l代表的是最后一个小于target
的下一个下标,而r代表的是大于等于target
的上一个下标,而本题要求第一个和最后一个元素位置,因此可以使用两次二分,分别找第一个最后一个。
代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 vector<int > searchRange (vector<int >& nums, int target) { int l = 0 , r = nums.size () - 1 ; int first = -1 , last = -1 ; while (l <= r) { int mid = (l + r) / 2 ; if (nums[mid] == target) { first = mid; r = mid - 1 ; } else if (nums[mid] > target) { r = mid - 1 ; } else { l = mid + 1 ; } } l = 0 ; r = nums.size () - 1 ; while (l <= r) { int mid = (l + r) / 2 ; if (nums[mid] == target) { last = mid; l = mid + 1 ; } else if (nums[mid] > target) { r = mid - 1 ; } else { l = mid + 1 ; } } return vector<int >{first, last}; }
总结 还是要使用相等这一利器,不能为了用之前的方法而硬解。此题会有找不到的情况,可能越界,必须使用相等。 而上一题
思路二 当找到target
时,将l
和r
缩小,直到nums[l]
和nums[r]
都等于target
,然后返回
当找不到target
时,循环终止,直接返回{ -1, -1}
代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 vector<int > searchRange (vector<int >& nums, int target) { int l = 0 , r = nums.size () - 1 ; while (l <= r) { int mid = (r - l) / 2 + l; if (nums[mid] < target) { l = mid + 1 ; } else if (nums[mid] > target) { r = mid - 1 ; } else { while (nums[l] != target) { l++; } while (nums[r] != target) { r--; } return vector<int >{l,r}; } } return {-1 ,-1 }; }
搜索旋转排序数组 题目 整数数组 nums
按升序排列,数组中的值 互不相同 。 在传递给函数之前,nums
在预先未知的某个下标 k
(0 <= k < nums.length
)上进行了 旋转 ,使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]
(下标 从 0 开始 计数)。例如, [0,1,2,4,5,6,7]
在下标 3
处经旋转后可能变为 [4,5,6,7,0,1,2]
。 给你 旋转后 的数组 nums
和一个整数 target
,如果 nums
中存在这个目标值 target
,则返回它的下标,否则返回 -1
。
代码 回想二分搜索的思想,一分为二,化繁为简! 本题刚拿到手可能会无从下手,想想该如何一分为二?
对于旋转后的数组,一分为二后一定有一半是有序的,另一半无序。 有序的那一半可以根据区间边界值判断target是否在该区间,无序的那一半同样可以根据边界值来判断(边界一定是最大的)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 int search (vector<int >& nums, int target) { int l = 0 , r = nums.size () -1 ; while (l <= r) { int mid = (l + r) >> 1 ; if (target == nums[mid]) return mid; if (nums[l] <= nums[mid]) { if (target >= nums[l] && target < nums[mid]) r = mid-1 ; else l = mid+1 ; } else { if (target > nums[mid] && target <= nums[r]) l = mid +1 ; else r = mid -1 ; } } return -1 ; }
总结 寻找旋转排序数组中的最小值 题目 已知一个长度为 n 的数组,预先按照升序排列,经由 1 到 n 次 旋转 后,得到输入数组。例如,原数组 nums = [0,1,2,4,5,6,7]
在变化后可能得到: 若旋转 4 次,则可以得到 [4,5,6,7,0,1,2]
若旋转 7 次,则可以得到 [0,1,2,4,5,6,7]
注意,数组 [a[0], a[1], a[2], ..., a[n-1]]
旋转一次 的结果为数组[a[n-1], a[0], a[1], a[2], ..., a[n-2]]
。给你一个元素值 互不相同 的数组 nums
,它原来是一个升序排列的数组,并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
代码 题目转换一下思路,其实就是找到最后一个小于ans
初始值的数(用到向上取整)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 int findMin (vector<int >& nums) { int ans = nums[0 ]; int l = 0 , r = nums.size () - 1 ; while (l <= r){ int m = (r - l + 1 ) / 2 + l; if (nums[l] < nums[m]){ if (nums[l] < ans){ ans = nums[l]; } l = m + 1 ; } else { if (nums[m] < ans){ ans = nums[m]; } r = m - 1 ; } } return ans; }
总结 向上取整在搜索最后一个满足条件时使用。