数组问题之二分查找专题
leetcode 33. 搜索旋转排序数组
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
你可以假设数组中不存在重复的元素。你的算法时间复杂度必须是 O(log n) 级别。
示例 1: 输入: nums = [4,5,6,7,0,1,2], target = 0 输出: 4
示例 2: 输入: nums = [4,5,6,7,0,1,2], target = 3 输出: -1
题目要求O（logN）的时间复杂度，基本可以断定本题是需要使用二分查找，怎么分是关键
由于题目说数字了无重复，举个例子
1 2 3 4 5 6 7 可以大致分为两类,
第一类 2 3 4 5 6 7 1这种，也就是nums[start] <= nums[mid]。此例子中就是2 <= 5
这种情况下，前半部分有序。因此如果 nums[start] <=target<nums[mid]。则在前半部分找，
否则去后半部分找。
第二类 6 7 1 2 3 4 5这种，也就是nums[start] > nums[mid]。此例子中就是6 > 2
这种情况下，后半部分有序。因此如果 nums[mid] <target<=nums[end]。则在后半部分找，
否则去前半部分找。
public int search(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return -1;
}
int start = 0;
int end = nums.length - 1;
int mid;
while (start <= end) {
mid = start + (end - start) / 2;
if (nums[mid] == target) {
return mid;
}
//前半部分有序,注意此处用小于等于
if (nums[start] <= nums[mid]) {
//target在前半部分
if (target >= nums[start] && target < nums[mid]) {
end = mid - 1;
} else {
start = mid + 1;
}
} else {
if (target <= nums[end] && target > nums[mid]) {
start = mid + 1;
} else {
end = mid - 1;
}
}
}
return -1;
} leetcode 81. 搜索旋转排序数组 II
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。
编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true，否则返回 false。
示例 1: 输入: nums = [2,5,6,0,0,1,2], target = 0 输出: true
示例 2: 输入: nums = [2,5,6,0,0,1,2], target = 3 输出: false
和上一题类似，区别在于本题数组可以重复，因此多了一个nums[start] == nums[mid]的判断。
此种情况下，我们进行start++，将第一个数排除。
public boolean search(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return false;
}
int start = 0;
int end = nums.length - 1;
int mid;
while (start <= end) {
mid = start + (end - start) / 2;
if (nums[mid] == target) {
return true;
}
//前半部分有序
if (nums[start] < nums[mid]) {
//target在前半部分
if (nums[mid] > target && nums[start] <= target) {
end = mid - 1;
} else { //否则，去后半部分找
start = mid + 1;
}
} else {
if (nums[start] == nums[mid]) {
start++;
} else {//后半部分有序
//target在后半部分
if (nums[mid] < target && nums[end] >= target) {
start = mid + 1;
} else { //否则，去后半部分找
end = mid - 1;
}
}
}
}
//一直没找到，返回false
return false;
} leetcode 69. x 的平方根
实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
示例 1: 输入: 4 输出: 2
示例 2: 输入: 8 输出: 2
说明: 8 的平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
本题的考察点主要是二分查找。
还有一点需要注意的是，防止越界。可以用long来处理。但是long会占用更多的内存。
此处用了点小技巧，具体见代码。
public int mySqrt(int x) {
if (x == 1 || x == 0) {
return x;
}
int start = 1;
int end = x / 2 + 1;
int mid = 0;
while (start <= end) {
mid = start + (end - start) / 2;
//防止越界
if (mid <= x / mid && (mid + 1) > x / (mid + 1)) {
return mid;
}
if (mid > x / mid) {
end = mid - 1;
} else {
start = mid + 1;
}
}
return mid;
} leetcode 4. 寻找两个有序数组的中位数
给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。
示例 1: nums1 = [1, 3] nums2 = [2] 则中位数是 2.0
示例 2: nums1 = [1, 2] nums2 = [3, 4] 则中位数是 (2 + 3)/2 = 2.5
题目要求时间复杂度为O(log(m + n))。基本可以确定本题应该用二分查找，对于数组arr的中位数，如果数组长度为len，
len为奇数，则中位数为第（len+1）/2 位，如果len为偶数，我们需要知道第 len/2和 len/2+1 个数。我们需要找出两个排序数组的第k个数的问题。比较两个数组的第k/2位，然后将第k/2位较小的数组中的前k/2位删除。
然后继续此过程，举个例子
A={1,3,4,9} lenA=4 B={1,2,3,4,5,6,7,8,9} lenB=9 lenA+lenB=13 ，因此找第7个数
7/2 = 3 A的第3个数为4，B的第3个数为3， 因此接下来A={1,3,4,9} B={4,5,6,7,8,9} 找第7-3=4个数，
4/2=2 A的第2个数为3，B的第3个数为6， 因此接下来A={4,9} B={4,5,6,7,8,9} 找第4-2=2个数，
2/2=1 A的第1个数为4，B的第1个数为4， 因此接下来A={4} B={5,6,7,8,9} 找第2-1=1个数，
现在找第1个数，比较A[0]和B[0]谁更小即可，因此最后结果为4
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int len1 = nums1.length;
int len2 = nums2.length;
return (find(nums1, 0, len1 - 1, nums2, 0, len2 - 1, (len1 + len2 + 1) / 2) + find(nums1, 0, len1 - 1, nums2, 0, len2 - 1, (len1 + len2) / 2 + 1)) * 0.5;
}
private int find(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int cnt) {
int len1 = end1 - start1 + 1;
int len2 = end2 - start2 + 1;
//确保nums1是短的
if (len1 > len2) {
return find(nums2, start2, end2, nums1, start1, end1, cnt);
}
//如果len1已经为空，直接从nums2找
if (len1 == 0) {
return nums2[start2 + cnt - 1];
}
//找第1个数，比较nums1[0]和nums2[0]谁更小即可
if (cnt == 1) {
return Math.min(nums1[start1], nums2[start2]);
}
//因为nums1比较短，因此取位置时要考虑实际长度
int pos1 = start1 + Math.min(cnt / 2, len1) - 1;
int pos2 = start2 + cnt / 2 - 1;
if (nums1[pos1] > nums2[pos2]) {
return find(nums1, start1, end1, nums2, pos2 + 1, end2, cnt - cnt / 2);
} else {
return find(nums1, pos1 + 1, end1, nums2, start2, end2, cnt - Math.min(cnt / 2, len1));
}
} leetcode 35. 搜索插入位置
public int searchInsert(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return 0;
}
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;
} leetcode 74. 搜索二维矩阵
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0) {
return false;
}
int row = matrix.length;
int col = matrix[0].length;
int start = 0;
int end = row * col - 1;
while (start <= end) {
int mid = start + (end - start) / 2;
if (matrix[mid / col][mid % col] == target) {
return true;
}
if (matrix[mid / col][mid % col] > target) {
end = mid - 1;
} else {
start = mid + 1;
}
}
return false;
}
投递理想汽车等公司10个岗位 >