E

EdwardWong

V1

2022/09/13阅读:11主题:姹紫

二分法总结

二分查找的前提有序数组且无重复元素, 如果有重复元素的话,会出现使用二分查找返回的元素下标不唯一的情况。

关于二分法的区间选择,可以查看二分法及C++之Vector容器

LeetCode 704 二分查找

题目描述

给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。

示例1:

输入: nums = [-1,0,3,5,9,12], target = 9     
输出: 4
解释: 9 出现在 nums 中并且下标为 4

示例2

输入: nums = [-1,0,3,5,9,12], target = 2   
输出: -1
解释: 2 不存在 nums 中因此返回 -1

提示:

- 你可以假设 nums 中的所有元素是不重复的。
- n 将在 [1, 10000]之间。
- nums 的每个元素都将在 [-9999, 9999]之间。

解法一:二分查找

class Solution{
public:
int search(vector<int>& array, int target){
int left=0;
int right=array.size()-1;
while(left<=right){
int middle=left+(right-left)/2;
if(array[middle]>target){
right=middle-1;
}else if(array[middle]<target){
left=middle+1;
}else {
return middle;
}

}
return -1;
}
};

解法二:暴力解法

class Solution {   
public:
int search(vector<int>& nums, int target) {
int i;
int a=nums.size()-1;
for( i=0;i<=a;i++){
if (nums[i]==target) {
return i;
break; // break退出循环
}
}
return -1;
}
};

LeetCode 35 搜索插入位置

题目描述

给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

示例1:

输入: nums = [1,3,5,6], target = 5
输出: 2

示例2:

输入: nums = [1,3,5,6], target = 2
输出: 1

示例3:

输入: nums = [1,3,5,6], target = 7
输出: 4

提示:

1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 为 无重复元素 的 升序 排列数组
-104 <= target <= 104

解题代码


class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int left=0;
int right=nums.size()-1;
while(left<=right){
int middle=left+(right-left)/2;
if (nums[middle]<target){
left=middle+1;
}else if(nums[middle]>target){
right=middle-1;
}else{
return middle;
}
}
return right+1; //注意此时要返回right+1
}
};

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

题目描述:

给你一个按照非递减顺序排列的整数数组nums,和一个目标值target。请你找出给定目标值在数组中的开始位置和结束位置. 如果数组中不存在目标值target,返回 [-1, -1]。 你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例1:

输入:nums = [5,7,7,8,8,10], target = 8
输出:[3,4]

示例2:

输入:nums = [5,7,7,8,8,10], target = 6
输出:[-1,-1]

示例3:

输入:nums = [], target = 0
输出:[-1,-1]

解题思路:

寻找target在数组中的左右边界,有如下三种情况:

  • 情况一: 数组元素target没有在数组中,此时返回(-1,-1)

  • 情况二: 数组元素target在数组中,此时返回元素的第一个元素和最后一个元素

  • 情况三: 数组元素target在数组范围中,但是不存在于数组中。

解题代码:

二分法

class Solution {
public:

int Right=-2;
int Left=-2;
vector<int> searchRange (vector<int>& nums, int target) {
if(nums.size()==0) return{-1,-1}; // return 会退出函数
Right=FindRight(nums,target);
Left=FindLeft(nums,target);
// 如果数组中没有元素,那么返回(-1,-1)
if(Right==-2||Left==-2) return{-1,-1};
if(Right-Left>1) return{Left+1,Right-1};
return{-1,-1};
}

int FindRight(vector<int>& nums, int target){
int left=0;
int right=nums.size()-1;
while(left<=right){
int middle=left+(right-left)/2;
if (nums[middle]<=target){
left=middle+1;
Right=left;
}else{
right=middle-1;
}
}
return Right;
}

int FindLeft(vector<int>& nums, int target){
int left=0;
int right=nums.size()-1;
while(left<=right){
int middle=left+(right-left)/2;
if (nums[middle]>=target){
right=middle-1;
Left=right;
}else{
left=middle+1;
}
}
return Left;
}
};

对于情况二,会出现left=right的情况,不满足right-left>1的情况

暴力解法

LeetCode 69 x的平方根

题目描述:

给你一个非负整数 x ,计算并返回 x 的 算术平方根 。

示例1:

输入:x = 4
输出:2
输入:x = 8
输出:2
解释:8 的算术平方根是 2.82842..., 由于返回类型是整数,小数部分将被舍去。

解题思路

使用二分法求解时,引入一个temp变量,并用left+(right-left)/2作为middle, 最后的结果需要保证temp < x/middle

解法一: 二分法

class Solution {
public:
int left;
int right;
int mySqrt(int x) {
if (x==0) return 0;
if (x==1) return 1;
if(x!=0 && x!=1) {
left=0;
right=x;
while(left<=right){
int middle=left+(right-left)/2;
int temp=x/middle; // 最后的结果是temp肯定不能比middle大
if(temp<middle){
right=middle-1;
} else if(temp >middle){ //如果temp比middle大,说明需要增大middle,从而减小temp
left=middle+1;
} else if(temp==middle) { //此时函数返回值是middle, 如果不相等的时候,也需要一个返回值。
return middle;
}
}
}
return right; //此处也需要返回值以应对最后的temp不等于middle时没有返回值的情况
}
}

解法二: 牛顿迭代法

待补充

分类:

后端

标签:

后端

作者介绍

E
EdwardWong
V1