leetcode高频题笔记之二分查找

69.x的平方根

在这里插入图片描述
去除x==0和x==1的情况，然后从1到x进行二分查找

public class Solution {

    public int mySqrt(int x) {
        if (x == 0 || x == 1) return x;
        int left = 1;
        int right = x;
        while (left <= right) {
            int mid = left + (right - left) / 2;//防止越界，用减法或者位运算
//            int mid = (right + left) >> 1;
            if (mid > x / mid) right = mid - 1;//除法防止越界
            else left = mid + 1;
        }
        return right;
    }
}

牛顿迭代法：
参考题解

class Solution {
    public int mySqrt(int x) {
        long r = x;
        while (r * r > x) {
            r = (r + x / r) / 2;
        }
        return (int)r;
    }
}

367.有效的完全平方数

在这里插入图片描述
二分查找

class Solution {
    public boolean isPerfectSquare(int num) {
        if (num == 1) return true;
        long left = 2;
        long right = num / 2;
        while (left <= right) {
            long mid = (left + right) >> 1;
            if (mid * mid == num) return true;
            else if (mid > num / mid) right = mid - 1;
            else left = mid + 1;
        }
        return false;
    }
}

牛顿迭代法
迭代求算数平方根，如果算数平方根的平方还是num，说明是完全平方数

public class Solution {
    public boolean isPerfectSquare(int num) {
        if (num < 2) return true;
        long a = num;
        while (a * a > num) {
            a = (a + num / a) / 2;
        }
        return a * a == num;
    }
}

33.搜索旋转排序数组

在这里插入图片描述
二分查找：每次查找必有一边是有序的！找到有序的一边，判断target在不在里面

class Solution {
    public int search(int[] nums, int target) {

        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = (left + right) >> 1;
            if (target == nums[mid]) return mid;//找到结果
            //前半段有序（可能的情况：456123,444123，因为旋转前是有序的，所以这个条件一定满足）
            if (nums[left] <= nums[mid]) {
                //taget在前半段，mid位置已经判断了，left位置还需要判断
                if (target < nums[mid] && target >= nums[left]) {
                    right = mid - 1;
                } else {//不在前半段
                    left = mid + 1;
                }
            } else {//后半段有序（可能情况：561234）
                //target在后半段，mid位置已经判断了，right位置还需要判断
                if (target > nums[mid] && target <= nums[right]) {
                    left = mid + 1;
                } else {//不在后半段
                    right = mid - 1;
                }

            }
        }
        //没找到
        return -1;
    }
}

74.搜索二维矩阵

在这里插入图片描述
二分查找：
将二维数组当成一维进行查找

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;

        int m = matrix.length;
        int n = matrix[0].length;
        int left = 0;
        int right = m * n - 1;
        while (left <= right) {
            int mid = (left + right) >>> 1;
            if (target == matrix[mid / n][mid % n]) return true;
            if (target > matrix[mid / n][mid % n]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return false;
    }
}

右上角为起点的查找,查找状态树是一棵二叉搜索树

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;

        int m = matrix.length;
        int n = matrix[0].length;
        int i = 0;
        int j = n - 1;
        while (i < m && j >= 0) {
            if (matrix[i][j] == target) return true;
            else if ( target>matrix[i][j]) i++;
            else j--;
        }
        return false;
    }
}

153.寻找旋转排序数组中的最小值

在这里插入图片描述
如果nums[left] <= nums[right]说明这一段有序，且是我们选择的包含拐点的部分
如果没有序，二分查询无序部分

class Solution {
    public int findMin(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            if (nums[left] <= nums[right]) {
                return nums[left];
            }
            int mid = (left + right) >> 1;
            //有序在左边，就去右边查找
            if (nums[mid] >= nums[left]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return nums[left];
    }
}

class Solution {
    public int findMin(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {

            int mid = (left + right) >> 1;
            //后半段无序
            if (nums[mid] > nums[right]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return nums[left];
    }
}

744.寻找比目标字母大的最小字母

在这里插入图片描述
题意：给定一个循环有序的字符数组 letters 和一个字符 target，要求找出 letters 中大于 target 的最小字符，如果
找不到就返回第 1 个字符。

public class Solution {
    public char nextGreatestLetter(char[] letters, char target) {
        int left = 0;
        int right = letters.length - 1;
        while (left <= right) {
            int mid = (left + right) >> 1;
            if (letters[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left < letters.length ? letters[left] : letters[0];
    }
}

540.有序数组中的单一元素

在这里插入图片描述
针对偶数位的二分查找
计算中点，如果中点下标为奇数，让其减1，保证mid是每一组两个数的开头
比较mid下标值和mid+1下标值，如果相同说明这个数有两个，left右移两位，否则这个位置及之前出现了1个数的，将right设置为mid

public class Solution {
    public int singleNonDuplicate(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int mid = (left + right) >> 1;
            if (mid % 2 == 1) {
                mid--;//保证查找区间大小保持奇数,保证mid是一组的开始
            }
            if (nums[mid] == nums[mid + 1]) {
                left = mid + 2;
            } else {
                right = mid;
            }
        }
        return nums[left];
    }
}

278.第一个错误的版本

在这里插入图片描述
二分查找，如果查找节点是错误版本，则第一个错误点在当前节点及之前；如果查找节点不是错误版本，则第一个错误点在当前节点之后

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int left = 1;
        int right = n;
        while (left < right) {
            int mid = (left + right) >>> 1;
            if (isBadVersion(mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

34.在排序数组中查找元素的第一个和最后一个位置

在这里插入图片描述
通过二分查找找到target，然后移动两个指针找到左右边界

public class Solution {
    public int[] searchRange(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {
            int mid = (left + right) >>> 1;
            if (nums[mid] == target) {
                int l = mid;//左边界
                int r = mid;//右边界
                while (l - 1 >= 0 && nums[l] == nums[l - 1]) {
                    l--;
                }
                while (r + 1 < nums.length && nums[r] == nums[r + 1]) {
                    r++;
                }
                return new int[]{l, r};
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return new int[]{-1, -1};
    }
}

leetcode分类题集文章被收录于专栏

按知识点分类整理leetcode的题目和解法