刷题记录｜目标101题--二分查找
写在前面
关于二分法的左闭右闭还是左闭右开这篇文章写的比较好：https://zhuanlan.zhihu.com/p/141480088
No.1 Sqrt(x)
题目链接：https://leetcode.com/problems/sqrtx/
涉及到的算法：二分法
解题思路：
这里注意三个点，1.我们要使用左闭右闭，不然可能走不出循环
2. 如果是单调递增的函数则return r，反之return l
3。要使用除法，如果使用加***溢出
class Solution {
public int mySqrt(int x) {
if (x == 0 || x == 1) return x;
int left = 1, right = x,mid = 0;
while (left <= right) {
mid = left + (right - left) / 2;
int sqrt = x / mid;
if (sqrt == mid) return mid;
if (sqrt < mid) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return right;
}
}
No. 2 Find First and Last Position of Element in Sorted Array
题目链接：https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/
解题方法：二分
解题思路：注意在while里循环的时候也要注意数组边界
class Solution {
public int[] searchRange(int[] nums, int target) {
int l = 0, r = nums.length - 1;
int[] temp_result = {0,0};
if (nums.length == 1 && nums[0] == target) return temp_result;
int[] result = {-1,-1};
while (l <= r) {
int mid = l + (r - l)/2;
if (nums[mid] == target) {
int begin = mid, end = mid;
while(begin >= 0 && nums[begin] == target) {
result[0] = begin--;
}
while(end < nums.length && nums[end] == target) {
result[1] = end++;
}
break;
} else if (nums[mid] < target) {
l = mid + 1;
} else {
r = mid - 1;
}
}
return result;
}
} No.3 Search in Rotated Sorted Array II
题目链接：https://leetcode.com/problems/search-in-rotated-sorted-array-ii/
涉及到的算法：二分法
解题思路：
不需要找出究竟是在哪个点rotate的，只需要知道，如果nums[mid]>nums[l] 则左区间一定单调增，反之右区间一定单调增即可减少二分的步骤
注意这当nums[mid] == nums[l]的时候，无法区分究竟是左区间完全相同还是右区间完全相同，所以可以单纯的移动l++
class Solution {
public boolean search(int[] nums, int target) {
if (target == nums[0]) return true;
int l = 0, r = nums.length - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (nums[mid] == target) return true;
if (nums[mid] == nums[l]) {
l++;
} else if (nums[mid] < nums[l]) {
if (target > nums[mid] && target <= nums[r]) {
l = mid + 1;
} else {
r = mid - 1;
}
} else {
if (target >= nums[l] && target < nums[mid]) {
r = mid - 1;
} else {
l = mid + 1;
}
}
}
return false;
}
} No.4 Find Minimum in Rotated Sorted Array II
题目链接：https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/
解题思路：旋转数组的变形题，使用和旋转数组一样的思路。
每次得到一个单调区间，获取最小值，直至结束，注意如果nums[mid] == nums[l]时无法分辨大小，则单纯++
class Solution {
public int findMin(int[] nums) {
if (nums.length == 1) return nums[0];
if (nums.length == 2) return (nums[0] > nums[1]) ? nums[1] : nums[0];
int l = 0, r = nums.length - 1, min = Integer.MAX_VALUE;
while (l <= r) {
int mid = l + (r - l) / 2;
if (nums[mid] == nums[l]) {
min = Math.min(min,nums[l]);
l ++;
} else if (nums[mid] > nums[l]) {
min = Math.min(min,nums[l]);
l = mid + 1;
} else {
min = Math.min(min,nums[mid]);
r = mid - 1;
}
}
return min;
}
} No. 5 Single Element in a Sorted Array
题目链接：https://leetcode.com/problems/single-element-in-a-sorted-array/
解题思路：二分法
这题的重点在与奇偶位数的变化。
- 如果mid是偶数，则
-
- 假如这个单身狗数没有出现，他应该和mid+1是一对组合，所以可以更新l
- 假如这个单数已经出现过了，则他应该和mid-1是一对，则更新r
- 如果这个mid是奇数
-
- 假如这个单身狗数没有出现，他应该和mid-1是一对组合，所以可以更新l
- 假如这个单数已经出现过了，则他应该和mid-1是一对，则更新r
class Solution {
public int singleNonDuplicate(int[] nums) {
if (nums.length == 1) return nums[0];
if (nums.length == 3) return nums[0] == nums[1] ? nums[2] : nums[0];
int l = 0, r = nums.length - 1;
while (l <= r - 3) {
int mid = l + (r - l) / 2;
if (nums[mid - 1] != nums[mid] && nums[mid + 1] != nums[mid]) {
return nums[mid];
} else if (mid %2 == 0) {
if (nums[mid] == nums[mid + 1]) {
l = mid + 2;
} else {
r = mid - 2;
}
} else {
if (nums[mid] == nums[mid - 1]) {
l = mid + 1;
} else {
r = mid - 1;
}
}
}
if (l == r) return nums[l];
return nums[l] == nums[l + 1] ? nums[r] : nums[l];
}
} No. 6 Median of Two Sorted Arrays
题目链接：https://leetcode.com/problems/median-of-two-sorted-arrays/
解题思路：
这题的重点思路是：
两个数组找中位数，其实意味着寻找这个两个数组合并后的第k个元素的值，如果两个数组的位数是偶数，则分别寻找k-1和k求中位数，奇数则是第k个数字。
利用二分法，左边与右边各求一个中位数，如果nums1.mid < nums2.mid，则利用他们的递增性，可以抛弃nums1.left，下次循环去找nums1.right+nums2,反之找nums1+nums2.left.
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.length, n = nums2.length;
return (getKthNumberInSortedArrays(nums1,0,nums2,0,(m + n + 1) / 2) +
getKthNumberInSortedArrays(nums1,0,nums2,0,(m + n + 2) / 2) ) / 2;
}
private double getKthNumberInSortedArrays(int[] nums1,int start1, int[] nums2, int start2, int k) {
if (start1 >= nums1.length) return nums2[start2 + k - 1];
if (start2 >= nums2.length) return nums1[start1 + k - 1];
if (k == 1) return Math.min(nums1[start1],nums2[start2]);
int mid1 = start1 + k / 2 - 1;
int mid2 = start2 + k / 2 - 1;
int val1 = mid1 >= nums1.length ? Integer.MAX_VALUE : nums1[mid1];
int val2 = mid2 >= nums2.length ? Integer.MAX_VALUE : nums2[mid2];
if (val1 < val2) {
return getKthNumberInSortedArrays(nums1,start1 + k/2,nums2,start2,k - k/2);
} else {
return getKthNumberInSortedArrays(nums1,start1,nums2,start2 + k/2,k - k/2);
}
}
} 
联想公司福利 620人发布
