2G的剩余内存空间，如果这2G的内存空间不连续那也无法申请到1G大小的数组空间，所以我们说数据量太大也不适合用二分查找。
2、面试实战
69. x 的平方根
字节跳动，美团点评最近面试题，69. x 的平方根
class Solution {
// 求sqrt(x)即求：x=n^2 (n>0),就是我们所熟知的抛物线(y=x^2)右侧，单调递增,且有上下界,[1,x/2]
public int mySqrt(int x) {
//特殊判断
if (x <=1) {
return x;
}
//找一个数k,k^2<=x,找一个最大的k就是我们想要的
long left=1,right = x>>1,mid = 0;
while (left <=right ) {
mid = (left+right) >>1;
if (mid * mid < x) {
left = mid + 1;
}else if (mid * mid > x) {
right = mid - 1;
}else {
return (int)mid;
}
}
return (int)left-1;
}
}
代码解释：
1：如果正好找到一个mid^2 = x则在while loop中就可以直接返回了，
2：如果while loop中还没找到，就类似x=8，我们在[ 1，2，3，4 ]中去寻找，while loop中最后一次循环left == right == 3，我们只需找k^2 <=x的最大k值即可。
进阶：牛顿迭代法解决该问题！参考精选题解：https://leetcode-cn.com/problems/sqrtx/solution/er-fen-cha-zhao-niu-dun-fa-python-dai-ma-by-liweiw/方法二
同类题目：367. 有效的完全平方数
class Solution {
public boolean isPerfectSquare(int x) {
//特殊判断
if (x <=1) {
return true;
}
long left=1,right = x>>1,mid = 0;
while (left <=right ) {
mid = (left+right) >>1;
if (mid * mid < x) {
left = mid + 1;
}else if (mid * mid > x) {
right = mid - 1;
}else {
return true;
}
}
return false;
}
}
33. 搜索旋转排序数组
字节，快手，百度最近面试题，33. 搜索旋转排序数组
二分查找的变形题目
思考要点：
1：二分的条件：满足有上下边界，数组存储可利用下标获取，单调性这块原始数组是单调递增的，旋转之后虽然整体不是单调性的，但是其中有一半一定是单调递增的。
2：要达到log n的复杂度肯定是要二分，但是并不能简单套用二分的模板，我们需要先找到哪半部分是具备单调性的，并判断target是否在该范围内，如果在则在这部分查找target，如果不在则在另外半部分查找。
class Solution {
public int search(int[] nums, int target) {
//此处left，right代表的是下标
int left=0,right = nums.length-1,mid=0;
while (left <= right) {
mid = (left+right) >>1;
if (nums[mid] == target) {
return mid;
}
//前半部分有序
if (nums[left] <= nums[mid]) {
//target如果在前半部分则在前半部分找,否则在后半部分找
if (target < nums[mid] && target >=nums[left] ) {
right = mid -1;
}else {
left = mid + 1;
}
}else {
//后半部分有序
//target如果在后半部分则在后半部分找，否则在前半部分找
if (target > nums[mid] && target <= nums[right]) {
left = mid +1;
}else {
right = mid -1;
}
}
}
return -1;
}
}
153. 寻找旋转排序数组中的最小值
网易，拼多多，今日头条面试题，153. 寻找旋转排序数组中的最小值
class Solution {
//二分,但不能套用简单的二分模板,修改二分的判断条件
public int findMin(int[] nums) {
int left=0,right=nums.length-1,mid = 0;
/*
在这里如果left==right则可以直接返回了,最小元素一定是它
*/
while (left < right ) {
mid = (left + right) >>1;
if (nums[mid] < nums[right]) {//右区间连续,最小值一定在左半区间
//mid可能是最小值也可能不是，简单二分的模板代码写right=mid-1;
right = mid;
}else if (nums[mid] > nums[right]) { //右边区间不连续,最小值一定在该区间内
left = mid +1;
}
}
return nums[left];
}
}
进阶思考题：
使用二分查找，寻找一个半有序数组 [4, 5, 6, 7, 0, 1, 2] 中间无序的地方
74. 搜索二维矩阵
新浪，爱奇艺，三星面试题，74. 搜索二维矩阵
解题思路：标准的二分m x n的矩阵可以看成 m x n 的有序数组
参考官方题解：https://leetcode-cn.com/problems/search-a-2d-matrix/solution/sou-suo-er-wei-ju-zhen-by-leetcode/
class Solution {
//标准的二分m x n的矩阵可以看成 m x n 的有序数组
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length;
if (m ==0) {
return false;
}
int n = matrix[0].length;
int left = 0;
int right = m * n -1;
int mid=0,row=0,col=0;
while (left<=right) {
mid = (left+right)>>1;
//最重要的就是将mid转换陈二维数组中的下标。
row = mid / n;
col = mid % n;
if (matrix[row][col] == target) {
return true;
}else if (matrix[row][col] < target) {
left = mid +1;
}else {
right = mid-1;
}
}
return false;
}
}
本文由传智教育博学谷教研团队发布。
如果本文对您有帮助，欢迎关注和点赞；如果您有任何建议也可留言评论或私信，您的支持是我坚持创作的动力。
转载请注明出处！