hot100之二分查找
搜索插入位置(035)class Solution {
public int searchInsert(int[] nums, int target) {
int n = nums.length;
int lef = -1;
int rig = n;
while(lef+1 < rig){
int mid = (lef + rig) / 2;
if (nums < target){
lef = mid;
}else rig = mid;
}
return rig;
}
}
[*]分析
基础二分
搜索二维矩阵(074)
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length;
int n = matrix.length;
int lef = -1;
int rig = m*n;
while (lef+1 < rig){
int mid = (lef + rig) / 2;
int x = matrix;
if (x < target) lef = mid;
else if (x > target) rig = mid;
else return true;
}
return false;
}
}
[*]分析
把每一个row 横向相连, 作二分
在排序数组中查找元素的第一个和最后一个位置(034)
class Solution {
public int[] searchRange(int[] nums, int target) {
int start = searchLower(-1 ,nums, target);
if (start == nums.length || nums != target) return new int[]{-1,-1};
int end = searchLower(start, nums, target+1) -1;
return new int[] {start, end};
}
private int searchLower(int lef, int[] nums, int target){
int rig = nums.length;
while (lef + 1 < rig){
int mid = (lef + rig) / 2;
if (nums < target) lef = mid;
else rig = mid;
}
return rig;
}
}
[*]分析
通过两次二分 查找 target 和target+1的起始位置, 确定target的范围
搜索旋转排序数组(033)
class Solution {
public int search(int[] nums, int target) {
int n = nums.length -1;
int lef = -1;
int rig = n;
while (lef + 1< rig){
int mid = (lef + rig) / 2;
if (check(nums, target, mid)){ //target在mid右侧
lef = mid;
}else rig = mid;
}
return nums == target ? rig : -1;
}
private boolean check(int[] nums, int target, int idx){
int x = nums;
int end = nums;
if (x < end){
return x < target && target <= end;// mid在小端 且比target小
}
// mid在大端 且< target在小端 || target > mid >
return x < target || target <= end;
}
}
[*]分析
判断 mid 在 →
[*]感悟
二分用来查找数据的拐点,以作check()
寻找两个正序数组的中位数(004)
这题给我写晕厥了
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]