【算法练习】leetcode算法题合集之二分查找篇

二分查找

LeetCode69.x的平方根

只要小于等于就可以满足条件了。

class Solution {
    public int mySqrt(int x) {
        int left = 0, right = x;
        int ans = -1;
        while (left <= right) {
            int mid = (right - left) / 2 + left;
            if ((long) mid * mid <= x) {
                ans = mid;
                left = mid + 1;

            } else {
                right = mid - 1;
            }
        }
        return ans;
    }
}

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

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

二分查找获取元素的左边界

左边界是可能不存在的。

当target==nums[mid]，继续在左边寻找更合适的mid

寻找大于等于target的元素。如果有等于的元素，是可以返回的。如果有大于的元素，返回的结果是mid+1。

class Solution_LC34 {
    public int[] searchRange(int[] nums, int target) {
        int start = lowerBounds(nums, target);
        if (start == nums.length || nums[start] != target) {
            return new int[]{-1, -1};
        }
        int end = lowerBounds(nums, target + 1) - 1;
        return new int[]{start, end};
    }

    private int lowerBounds(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = (right - left) / 2 + left;
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
}

二维矩阵类

LeetCode74.搜索二维矩阵

找到最后一个不大于target的元素。比如[1,10,23]，target是3，获取到的元素为1。

等于直接获取low，进行二分的时候获取(high-low+1)/2。存在low=1，high=2，low一直为1的情况。

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int rowIndex = binarySearchFirstCol(matrix, target);
        if (rowIndex < 0 || rowIndex >= matrix.length) {
            return false;
        }
        return binarySearchRow(matrix[rowIndex], target);
    }

    private int binarySearchFirstCol(int[][] matrix, int target) {
        int low = -1, high = matrix.length - 1;
        while (low < high) {
            int mid = low + (high -low+1 ) / 2;
            if (matrix[mid][0] > target) {
                high = mid - 1;
            } else {
                low = mid;
            }
        }
        return low;
    }

    private boolean binarySearchRow(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = (right - left) / 2 + left;

            if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                return true;
            }
        }
        return false;
    }
}

LeetCode240.搜索二维矩阵II

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        for (int[] nums : matrix) {
            if (binarySearch(nums, target)) {
                return true;
            }
        }
        return false;
    }

    private boolean binarySearch(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = (right - left) / 2 + left;
            if (nums[mid] > target) {
                right = mid - 1;
               
            } else if (nums[mid] < target) {
                 left = mid + 1;
            } else {
                return true;
            }
        }
        return false;
    }
}

数组从左下角向右上方向移动，向上是变小，向右是变大。

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int i = matrix.length - 1, j = 0;
        while (i >= 0 && j < matrix[0].length) {
            if (matrix[i][j] > target) {
                i--;
            } else if (matrix[i][j] < target) {
                j++;
            } else {
                return true;
            }
        }
        return false;
    }

旋转数组类

LeetCode33.搜索旋转排序数组

寻找中间元素，判断是否找到；mid元素不是目标元素，判断mid元素是否在左升区间，如果在，判断目标元素是否在[left,mid]，缩小范围。

class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = (right - left) / 2 + left;
            if (nums[mid] == target) {
                return mid;
            }
            // left到mid之间是有序的。
            if (nums[mid] >= nums[left]) {
                if (target >= nums[left] && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }

            } else {
                if (target > nums[mid] && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }

        }
        return -1;

    }
}

LeetCode153.搜索旋转数组的最小值(**)

LeetCode153.搜索旋转数组的最小值

二分查找我原本以为很简单，但是里面的细节真的很多。

while (left <= right) 的终止条件是left>right，进行left = mid + 1;后nums[left]的性质就改变了。

nums[mid] == nums[left]，到底是修改left还是right，数组中存在两个元素，循环第一次获取到的nums[mid] == nums[left]，所以要比较第二遍。

class Solution {
    public int findMin(int[] nums) {
        int left = 0, right = nums.length - 1;
        int ans = Integer.MAX_VALUE;
        while (left <= right) {
            int mid = (right - left) / 2 + left;
            if (nums[mid] >= nums[left]) {
                ans = Math.min(ans, nums[left]);
                left = mid + 1;
            } else {
                ans = Math.min(ans, nums[mid]);
                right = mid - 1;
            }
        }
        return ans;

    }
}

nums[mid]<nums[right]，都意味着mid在右边升序段中。所以最小值在[left,mid]之间。

nums[mid] < nums[right]小于是符合条件的，所以right = mid;大于等于是不符合条件的，所以要 mid + 1

测试用例：数组[2,1]，发现2>1, left边界更新，当跳出循环，low变成相对大的元素。

数组升序 left–x 升序 x–right 升序

比较nums[left]还是nums[right]，因为nums[right]相对nums[mid]较大。在升序队列[1,2,3,4,5]中，nums[left]是最小的。比nums[left]大，无法判定最小值在[left,mid]还是[mid,right]之间。

class Solution {
    public int findMin(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = (right - left) / 2 + left;
            // 
            if (nums[mid] < nums[right]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return nums[left];
    }
}

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

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

如果小于最右边元素，说明在最小值在[left,mid]

如果大于最右边元素，说明最小值在[mid,right]

如果等于最右边的元素，无法判断，换下一个元素。

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

        while (left < right) {
            int mid = (right - left) / 2 + left;
            if (nums[mid] < nums[right]) {
                right = mid;
            } else if (nums[mid] > nums[right]) {
                left = mid + 1;
            } else {
                right = right - 1;
            }
        }
        return nums[left];

    }
}

找极大、极小值

LeetCode162.寻找峰值/极大值

LeetCode162.寻找峰值

判断如果nums[mid] > nums[mid + 1]，那么峰值在[left,mid]之间。

如果nums[mid] < nums[mid + 1]，峰值在[mid+1,right]之间

class Solution {
    public int findPeakElement(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = (right - left) / 2 + left;
            if (nums[mid] > nums[mid + 1]) {
                right = mid;
            } else if (nums[mid] < nums[mid + 1]) {
                left = mid + 1;
            }
        }
        return left;
    }
}

其他

寻找两个正序数组的中位数(**)

LeetCode4. 寻找两个正序数组的中位数

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int length1 = nums1.length;
        int length2 = nums2.length;
        int total = length1 + length2;
        if (total % 2 == 0) {
            return (getKth(nums1, nums2, total / 2 + 1) + getKth(nums1, nums2, total / 2)) / 2;
        } else {
            return getKth(nums1, nums2, total / 2 + 1);
        }
    }

    private double getKth(int[] nums1, int[] nums2, int k) {
        int length1 = nums1.length;
        int length2 = nums2.length;
        int index1 = 0;

        int index2 = 0;
        while (true) {
            // 边界情况
            if (index1 == length1) {
                return nums2[index2 + k - 1];
            }
            if (index2 == length2) {
                return nums1[index1 + k - 1];
            }
            if (k == 1) {
                return Math.min(nums1[index1], nums2[index2]);
            }
            int i1 = Math.min(nums1.length, k / 2 + index1) - 1;
            int i2 = Math.min(nums2.length, k / 2 + index2) - 1;
            int num1 = nums1[i1];
            int num2 = nums2[i2];
            if (num1 > num2) {
                k -= (i2 - index2 + 1);
                index2 = i2 + 1;
            } else {
                k -= (i1 - index1 + 1);
                index1 = i1 + 1;
            }
        }
    }
}

LeetCode287. 寻找重复数

原地hash修改数组，hash表需要额外空间

如果不允许重复的话，小于等于4的元素个数一定是小于等于4的。因为排序好了的数组4个位置放不下大于4个的元素。

class Solution {
    public int findDuplicate(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = (right - left) / 2 + left;
            int count = 0;
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] <= mid) {
                    count++;
                }
            }
            if (count > mid) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}