我要评论
1. 二分查找(难度:🟢1度)
- 题目描述
- 算法原理
a. 定义left ,right 指针，分别指向数组的左右区间。
b. 找到待查找区间的中间点mid,找到之后分三种情况讨论：
i. arr[mid] == target 说明正好找到，返回mid 的值；
ii. arr[mid] > target 说明[mid, right] 这段区间都是大于target 的，因此舍去右边区间，在左边[left, mid -1] 的区间继续查找，即让right = mid - 1 ，然后重复2 过程；
iii. arr[mid] < target 说明[left, mid] 这段区间的值都是小于target 的，因此舍去左边区间，在右边[mid + 1, right] 区间继续查找，即让left = mid + 1，然后重复2 过程；
c. 当left 与right 错开时，说明整个区间都没有这个数，返回-1 - 代码实现
class solution {
public int search(int[] nums, int target) {
int left = 0, right = nums.length-1;
while(left <= right){
int mid = left + (right-left)/2;
if (target < nums[mid]){
right = mid - 1;
}else if(target > nums[mid]){
left = mid + 1;
}else{
return mid;
}
}
return -1;
}
}
[注意事项]
- 计算mid的时候,没有使用
(left+right)/2,而是使用left+(right-left)/2的形式. - 二分法一般采用最中间的点作为划分点,其他的等分点也可以作为划分点,但是查找效率没有中间作为划分点高.
- 朴素二分模版总结
//首先定义left和right指针
while (left <= right){
int mid = left+(right-left)/2;
if(...) left = mid+1;
else if(...) right = mid-1;
else return ...;
}
2. 在排序数组中查找元素的第一个和最后一个位置(难度:🟡3度)
- 题目描述
- 算法原理
方便叙述，用x 表示该元素，resleft 表示左边界，resright 表示右边界- 寻找左边界
我们注意到以左边界划分的两个区间的特点：
▪ 左边区间[left, resleft - 1] 都是小于x 的；
▪ 右边区间（包括左边界） [resleft, right] 都是大于等于x 的；
• 因此，关于mid 的落点，我们可以分为下面两种情况：
◦ 当我们的mid 落在[left, resleft - 1] 区间的时候，也就是arr[mid] < target 。说明[left, mid] 都是可以舍去的，此时更新left 到mid + 1 的位置，这里需要注意在left上+1,因为mid左边的元素都已经小于目标值了,都可以舍去.继续在[mid + 1, right] 上寻找左边界；
◦ 当mid 落在[resleft， right] 的区间的时候，也就是arr[mid] >= target 。说明[mid + 1, right] （因为mid 可能是最终结果，不能舍去）是可以舍去的，此时更新right 到mid 的位置，由于mid的位置可能是最终的值,所以mid位置不可以舍去,不需要-1继续在[left, mid] 上寻找左边界；
• 由此，就可以通过⼆分，来快速寻找左边界；
[注意] 循环条件判断必须是left < right,如果加上等号,当找到目标值的时候.left和right重合,第一重合就证明已经找到了目标值,就没有必要再执行操作了,第二,如果找到了目标值,left和right依然会满足条件,会进入循环,会让程序陷入死循环.求中点的时候,必须采用向下取整的方式,如果采用向上取整,如果找到了目标值,right=mid的时候,right没有移动,就会陷入死循环. - 寻找右边界
与寻找左边界同理
◦ 用resright 表示右边界；
◦ 我们注意到右边界的特点：
▪ 左边区间（包括右边界） [left, resright] 都是小于等于x 的；
▪ 右边区间[resright+ 1, right] 都是大于x 的；
• 因此，关于mid 的落点，我们可以分为下面两种情况：
◦ 当我们的mid 落在[left, resright] 区间的时候，说明[left, mid - 1]（ mid 不可以舍去，因为有可能是最终结果）都是可以舍去的，此时更新left 到mid 的位置；
◦ 当mid 落在[resright+ 1, right] 的区间的时候，说明[mid, right] 内的元素是可以舍去的，此时更新right 到mid - 1 的位置；
• 由此，就可以通过⼆分，来快速寻找右边界；
- 寻找左边界
- 代码实现
class solution {
public int[] searchrange(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
int[] array = new int[2];
array[0] = -1;
array[1] = -1;
if (nums.length == 0){//注意处理特殊情况
return array;
}
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;//left下标不可能是t的值
} else {
right = mid;//right下标有可能是t的值
}
}
if (nums[left] == target){
array[0] = left;
}else{
return array;
}
left = 0;
right = nums.length - 1;
while (left < right) {
int mid = left + (right - left + 1) / 2;
if (nums[mid] > target) {
right = mid - 1; //right下标不可能是t的值
} else {
left = mid;//left下标可能是t的值
}
}
array[1] = right;
return array;
}
}
- 查找边界二分算法模版
- 左边界
while(left < right){ int mid = left+(right-left)/2; if(...) left = mid+1; else right = mid; }- 右边界
while(left < right){ int mid = left+(right-left+1)/2; if(...) left = mid; else right = mid-1; }
3. 搜索插入位置(难度:🔵2度)
- 题目解析
- 算法原理
a. 分析插⼊位置左右两侧区间上元素的特点：
设插⼊位置的坐标为 index ，根据插⼊位置的特点可以知道：
• [left, index - 1] 内的所有元素均是小于 target 的；
• [index, right] 内的所有元素均是大于等于 target 的。
b. 设 left 为本轮查询的左边界， right 为本轮查询的右边界。根据 mid 位置元素的信息，分析下⼀轮查询的区间：
▪ 当 nums[mid] >= target 时，说明 mid 落在了 [index, right] 区间上，mid 左边包括 mid 本身，可能是最终结果，所以我们接下来查找的区间在 [left,mid] 上。因此，更新 right 到 mid 位置，继续查找。
▪ 当 nums[mid] < target 时，说明 mid 落在了 [left, index - 1] 区间上，mid 右边但不包括 mid 本身，可能是最终结果，所以我们接下来查找的区间在 [mid+ 1, right] 上。因此，更新 left 到 mid + 1 的位置，继续查找。
c. 直到我们的查找区间的⻓度变为 1 ，也就是 left == right 的时候， left 或者right 所在的位置就是我们要找的结果 - 代码实现
class solution {
public int searchinsert(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid;
}
}
if (nums[right] < target) {
return right + 1;
}
return right;
}
}
4. x的平方根(难度:🔵2度)
- 题目描述
- 算法原理
设 x 的平方根的最终结果为 index ：
a. 分析 index 左右两次数据的特点：
▪ [0, index] 之间的元素，平方之后都是小于等于 x 的；
▪ [index + 1, x] 之间的元素，平方之后都是大于 x 的。
因此可以使用二分查找算法。 - 代码实现
class solution {
public int mysqrt(int x) {
if (x < 1){
return 0;
}
long left = 1;
long right = x;
while(left < right){
long mid = left + (right - left + 1)/2;//由于是向下取整,所以要加1
if (mid * mid <= x){
left = mid;
}else{
right = mid - 1;
}
}
return (int)left;
}
}
[注意] 我们这里使用long,防止数据溢出.
发表评论