Day01--二分查找

代码随想录https://www.programmercarl.com/0704.%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.html#%E6%80%BB%E7%BB%93
剑指offer题解：https://offer.hi-dhl.com/#/algorithm/03-number
《剑指offer>>全解https://fantianzuo.blog.csdn.net/article/details/107591709
https://github.com/doocs/leetcode/tree/main

本项目包含 LeetCode、《剑指 Offer（第 2 版）》、《剑指 Offer（专项突击版）》、《程序员面试金典（第 6 版）》等题目的相关题解。

https://www.xiehai.zone/JavaLeetCode/lcof1/03.html

二分查找

https://www.programmercarl.com/0704.%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.html#%E6%80%BB%E7%BB%93

704. 二分查找

力扣：https://leetcode.cn/problems/binary-search/

左闭右开

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

2.左闭右闭

class Solution {public int search(int[] nums, int target) {// 避免当 target 小于nums[0] nums[nums.length - 1]时多次循环运算if (target < nums[0] || target > nums[nums.length - 1]) {return -1;}int left = 0, right = nums.length - 1;while (left <= right) {int mid = left + ((right - left) >> 1);if (nums[mid] == target) {return mid;}else if (nums[mid] < target) {left = mid + 1;}else { // nums[mid] > targetright = mid - 1;}}// 未找到目标值return -1;}
}

在计算中间索引时，如果 left 和 right 是很大的整数（特别是在极端情况下，它们的和超过了整数类型的上限），直接使用 (left + right) / 2 可能会导致溢出。这是因为 left + right 可能会超出所能表示的最大值，从而导致结果不正确。

为了解决这个问题，可以使用以下公式来计算中间索引，以避免溢出：

mid = left + (right - left) / 2

这种写法首先减去 left 从而避免了直接相加，确保不会发生溢出。这样可以安全地计算中间索引。

35. 搜索插入位置simple

力扣：https://leetcode.cn/problems/search-insert-position/description/
解题思路：

1目标值在数组所有元素之前
2目标值等于数组中某一个元素
3目标值插入数组中的位置
4目标值在数组所有元素之后

左闭右闭

class Solution {public int searchInsert(int[] nums, int target) {int left=0,right=nums.length-1;while(left<=right){//直接用>>位运算符比/运算符要快int mid=left+((right-left)>>1);if(nums[mid]==target){return mid;}else if(nums[mid]<target){left=mid+1;}else right=mid-1;}return right+1;//134}
}

左闭右开

class Solution {public int searchInsert(int[] nums, int target) {int left=0,right=nums.length;while(left<right){//直接用>>位运算符比/运算符要快int mid=left+((right-left)>>1);if(nums[mid]==target){return mid;}else if(nums[mid]<target){left=mid+1;}else right=mid;}return right;//134}
}

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

力扣：https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/
解题思路：
共有三种情况：

情况一：target 在数组范围的右边或者左边，例如数组{3, 4, 5}，target为2或者数组{3, 4, 5},target为6，此时应该返回{-1, -1}
情况二：target 在数组范围中，且数组中不存在target，例如数组{3,6,7},target为5，此时应该返回{-1, -1}
情况三：target 在数组范围中，且数组中存在target，例如数组{3,6,7},target为6，此时应该返回{1, 1}
分别寻找左区间和右区间，左右根据左右区间做最后判断
比较好的题解链接：https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/solutions/536360/yi-wen-dai-ni-gao-ding-er-fen-cha-zhao-j-ymwl/

左闭右闭

class Solution {public int[] searchRange(int[] nums, int target) {int leftBorder=getLeftBorder(nums,target);int rightBorder=getRightBorder(nums,target);// 情况一:target在数组范围的右边或者左边if (leftBorder == -2 || rightBorder == -2) return new int[]{-1, -1};// 情况三：target 在数组范围中，且数组中存在targetif (rightBorder - leftBorder > 1) return new int[]{leftBorder + 1, rightBorder - 1};// 情况二：target 在数组范围中，且数组中不存在targetreturn new int[]{-1, -1};}int getRightBorder(int[] nums, int target) {int left = 0;int right = nums.length - 1;int rightBorder = -2; // 记录一下rightBorder没有被赋值的情况while (left <= right) {int middle = left + ((right - left) / 2);if (nums[middle] > target) {right = middle - 1;} else { // 寻找右边界，nums[middle] == target的时候更新leftleft = middle + 1;rightBorder = left;}}return rightBorder;}int getLeftBorder(int[] nums, int target) {int left = 0;int right = nums.length - 1;int leftBorder = -2; // 记录一下leftBorder没有被赋值的情况while (left <= right) {int middle = left + ((right - left) / 2);if (nums[middle] >= target) { // 寻找左边界，nums[middle] == target的时候更新rightright = middle - 1;leftBorder = right;} else {left = middle + 1;}}return leftBorder;}
}

class Solution {public int[] searchRange (int[] nums, int target) {int upper = upperBound(nums,target);int low = lowerBound(nums,target);  //不存在情况if (upper < low) {return new int[]{-1,-1};}return new int[]{low,upper};}//计算下边界int lowerBound(int[] nums, int target) {int left = 0, right = nums.length - 1;while (left <= right) {//这里需要注意，计算midint mid = left + ((right - left) >> 1);if (target <= nums[mid]) {//当目标值小于等于nums[mid]时，继续在左区间检索，找到第一个数right = mid - 1;}else if (target > nums[mid]) {//目标值大于nums[mid]时，则在右区间继续检索，找到第一个等于目标值的数left = mid + 1;}}return left;}//计算上边界int upperBound(int[] nums, int target) {int left = 0, right = nums.length - 1;while (left <= right) {          int mid = left + ((right - left) >> 1);if (target >= nums[mid]) {left = mid + 1;               }else if (target < nums[mid]) {right = mid - 1;}            }return right;}
}

69. x的平方根medium

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

367. 有效的完全平方数simple

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

复杂度分析

时间复杂度：O(logn)，其中 n 为正整数 num 的最大值。

空间复杂度：O(1)。

33.搜索旋转排序数组medium

力扣：https://leetcode.cn/problemset/
参考：https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/solutions/536360/yi-wen-dai-ni-gao-ding-er-fen-cha-zhao-j-ymwl/

class Solution {public int search(int[] nums, int target) {int left=0;int right=nums.length-1;while(left<=right){int mid=left+((right-left)>>1);if(nums[mid]==target){return mid;}//落在同一数组的情况，同时落在数组1或数组2if(nums[mid]>=nums[left]){//target落在left和mid之间，则移动我们的right，完全有序的一个区间内查找if(nums[mid]>target&&target>=nums[left]){right=mid-1;//target落在right和Mid之间，有可能在数组1，也有可能在数组2}else if(target>nums[mid]||target<nums[left]){left=mid+1;}}//不落在同一数组的情况，left在数组1，mid落在数组2else if(nums[mid]<nums[left]){//有序的一段区间，target 在 mid 和 right 之间if (nums[mid] < target && target <= nums[right]) {left = mid + 1;// 两种情况，target 在left 和 mid 之间} else if (target < nums[mid] || target > nums[right]) {right = mid - 1;}}}return -1;}}

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

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-left)/2;if(nums[right]<nums[mid]){left=mid+1;}else if(nums[right]>nums[mid]) {right=mid;}else{right--;}}return nums[left];}
}

81. 搜索旋转排序数组II(medium)

力扣：https://leetcode.cn/problems/search-in-rotated-sorted-array-ii/

class Solution {public boolean search(int[] nums, int target) {int left=0;int right=nums.length-1;while(left<=right){int mid=left+((right-left)>>1);if(nums[mid]==target){return true;}if(nums[mid]==nums[left]){left++;continue;}//落在同一数组的情况，同时落在数组1或数组2if(nums[mid]>=nums[left]){//target落在left和mid之间，则移动我们的right，完全有序的一个区间内查找if(nums[mid]>target&&target>=nums[left]){right=mid-1;//target落在right和Mid之间，有可能在数组1，也有可能在数组2}else if(target>nums[mid]||target<nums[left]){left=mid+1;}}//不落在同一数组的情况，left在数组1，mid落在数组2else if(nums[mid]<nums[left]){//有序的一段区间，target 在 mid 和 right 之间if (nums[mid] < target && target <= nums[right]) {left = mid + 1;// 两种情况，target 在left 和 mid 之间} else if (target < nums[mid] || target > nums[right]) {right = mid - 1;}}}return false;}
}

153.寻找旋转数组中的最小值(medium)

力扣：
解题思路：

数组完全有序nums[left]<nums[right],返回nums[left]
left和Mid都在前半部分，单调递增区间,left=mid+1
left在前半部分，mid在后半部分，right=mid

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-left)/2;if(nums[left]<=nums[mid]){left=mid+1;}else {right=mid;}}return -1;}
}

74. 搜索二维矩阵medium

力扣：https://leetcode.cn/problems/search-a-2d-matrix/description/

class Solution {public boolean searchMatrix(int[][] matrix, int target) {int left=0;int n=matrix[0].length;int m=matrix.length;int right=m*n-1;while(left<=right){int mid=left+(right-left)/2;int nums=matrix[mid/n][mid%n];if(nums==target){return true;}else if(nums<target){left=mid+1;}else{right=mid-1;}}return false;}
}

441.排列硬币(simple)

class Solution {public int arrangeCoins(int n) {int left = 1, right = n;while (left < right) {int mid = (right - left + 1) / 2 + left;if ((long) mid * (mid + 1) <= (long) 2 * n) {left = mid;} else {right = mid - 1;}}return left;
}
}

162.寻找峰值(medium)

参考链接：hhttps://leetcode.cn/problems/find-peak-element/solutions/6695/hua-jie-suan-fa-162-xun-zhao-feng-zhi-by-guanpengc

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

4.寻找两个正序（困难）

解题思路：参考链接https://blog.lichangao.com/daily_practice/leetcode/array/other.html#_0004-%E5%AF%BB%E6%89%BE%E4%B8%A4%E4%B8%AA%E6%AD%A3%E5%BA%8F%E6%95%B0%E7%BB%84%E7%9A%84%E4%B8%AD%E4%BD%8D%E6%95%B0
给定两个数组A、B,如何找到从小到大排列的第K个数？
只要让k取值(n+m)/2,就可以得到中位数。令k1=k/2,k2=k-k/2,则：

当A[k1]<B[k2]时，去掉A[<=k1]的元素
当A[k1]>B[k2]时，去掉B[<=k2]的元素
当A[k1]=B[k2]时，去掉A[<=k1]或B[<=k2]的元素
综上，可以将其转化为一个递归的问题，每次k的规模都减少一半，而k取值(n+m)/2

class Solution {public int find(int[] nums1,int i,int[] nums2,int j,int k){// 保证 nums1 的元素更少，方便处理if (nums1.length - i > nums2.length - j) return find(nums2, j, nums1, i, k);// nums1 为空，直接取 nums2 的第 k 个元素if (nums1.length == i) return nums2[j + k - 1];// k = 1 时，取两数组第一个元素的最小值if (k == 1) return Math.min(nums1[i], nums2[j]);// 分别对应两数组 k / 2 的下一个位置int si = Math.min((int)nums1.length, i + k / 2);int sj = j + k - k / 2;if (nums1[si - 1] < nums2[sj - 1]) {return find(nums1, si, nums2, j, k - (si - i));} else {return find(nums1, i, nums2, sj, k - (sj - j));}}public double findMedianSortedArrays(int[] nums1, int[] nums2) {int n=nums1.length+nums2.length;if(n%2==0){int left=find(nums1,0,nums2,0,n/2);int right=find(nums1,0,nums2,0,n/2+1);return (left+right)/2.0;}else{return find(nums1,0,nums2,0,n/2+1);}}}