1.leetcode (.704)⼆分查找
1.2算法原理
二分算法的满足条件是数组有序，其实并不严谨，实际上是要具有二段性，即通过有一个数能将数组分为两部分，一次比较能筛选掉一部分
循环结束条件：
left>right,因为每个区间内的数都是未知的，即使最后left和right相等还是要根目标值比较一次，来证明一个数是否有存在
时间复杂度：
O(logN)和O(N)的效率差距很大，在int范围内，O(N)最多要比较执行4*10^9次，而O(logN)最多只要32次
数据溢出问题：
(left + right) / 2 :
在大多数情况下是安全的,但如果 left 和 right 的和超过了该类型能表示的最大值，直接相加可能会导致整数溢出
left + (right - left) / 2 可以避免这个问题，利用起始值+偏移值可以有效避免两数相加超出范围，结果相同
至于left + (right - left+1) / 2和(left + right+1) / 2要不要加1的问题，在数组数量为奇数时结果相同。不同在于数量为偶数时中间值有两个数，不加1和加1计算结果一个在左中间值一个在右中间值，并不影响最终结果
1.3总结模板
该模板为最朴素的二分查找模板，适用范围一般限制较多，后续会总结左右边界的判断模板，为万能模板，适用范围更广
1.4代码
class Solution {
public:
int search(vector<int>& nums, int target) {
int left=0,right=nums.size()-1;
while(left<=right)
{
int mid=(left+right)/2;
if(nums[mid]<target) left=mid+1;
else if(nums[mid]>target) right=mid-1;
else if(nums[mid]==target) return mid;
}
return -1;
}
};
2. (.34)在排序数组中查找元素的第⼀个和最后⼀个位置
非递减顺序排列就是递增序列或不变
2.1算法原理
由于该题给定数组要么是递增要么不变，可以用一个值划分两个区间，所以具有二段性，符合使用二分算法的条件
查找区间左端点
与上题总结的朴素模板相比，该题的判断条件要发生变化。根据举例找出一般规律
如图分析：
1.当x小于target(t)的时候，由于我们寻找左端点，并且mid下标对应的值就是x，那么区间[left,mid]中的值都小于t，可以全部舍弃，将left更新到mid+1下标处
2.为什么要将>和=条件放在一起分析？因为=时只是代表有可能找到了左端点，该题并未结束，不能作为结束条件返回结果，所以一起分析因为该区间包含了左端点
3.当x>=t时，由于mid位置有可能是左端点下标所以不能舍去，左端点一定在区间[left,mid]中，将right更新为mid
- 细节处理
1.循环条件的判断
循环条件为left<right：
数组内元素总共三种情况，存在左端点、元素全部小于目标值、全部大于目标值，当left==right时就是最终结果，无需判断。
如果判断当数组内元素全部小于目标值时left=mid+1刚好结束循环，但若元素大于等于目标值时right=mid会陷入死循环
2.求中点的操作：
1式在x<t时left=mid+1移动到right处结束循环，当x>=t时right=mid移动到left处结束循环
2式在x<t时left=mid+1移动到right+1处结束循环，但x>=t时right=mid位置不变会陷入死循环
查找区间右端点
同理通过分析例子得出一般规律
如图分析：
1.当x<=t时，区间[left,mid-1]可以舍弃掉，mid处有可能就是右端点，所以令left=mid，继续寻找
2.当x>t时，区间[mid,right]可以舍弃掉因为都大于右端点值，令right=mid-1，继续寻找
- 细节处理
1.循环条件
与寻找左端点相同，都是left<right
2.求中点方式
分析过程与求左端点思路相同，无非是当元素为偶数个时中间点有两个，取左还是右，当其中一个在x<=t条件下left==mid下标都未发生变化因此会陷入死循环，不再赘述。
2.2总结模板
画星部分不用特意去记，根据题意分析二段性就可以得出，求中间值的方法可以这么想，当求左端点时，当数组元素为偶数个数时中间值有两个，mid落在左边那个，对应的计算方法就不要+1，反之求右端点时mid落在中间值右边那个，计算方法要+1，循环判断条件都相同。
更万能的记忆的方法，当if条件语句中出现了减法，那么中间值的计算就要+1
2.3代码
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
//判断数组为空的情况
if(nums.size()==0) return {-1,-1};
//判断数组是否具有target元素
int n=0;
for(auto e: nums) if(e==target) n++;
if(n==0) return {-1,-1};
//查找左端点
int left=0,right=nums.size()-1;
while(left<right)
{
int mid=left+(right-left)/2;
if(nums[mid]<target) left=mid+1;
else right=mid;
}
//查找右端点
int l=0,r=nums.size()-1;
while(l<r)
{
int m=l+(r-l+1)/2;
if(nums[m]<=target) l=m;
else r=m-1;
}
return {left,r};//最后写左右都可以,它们最终会相遇
}
};
3. (.20) x 的平⽅根
3.1算法原理
1.暴力解法
依次枚举所有数的平方，枚举区间为整个数组不需要额外判断，当等于目标值时直接返回，大于时说明前一个为结果。需注意由于是相乘，有可能超过int的最大值，应该使用longlong类型
class Solution {
public:
int mySqrt(int x) {
// 由于两个较⼤的数相乘可能会超过 int 最⼤范围
// 因此⽤ long long
long long i = 0;
for (i = 0; i <= x; i++)
{
// 如果两个数相乘正好等于 x，直接返回 i
if (i * i == x) return i;
// 如果第⼀次出现两个数相乘⼤于 x，说明结果是前⼀个数
if (i * i > x) return i - 1;
}
// 为了处理oj题需要控制所有路径都有返回值
return -1;
}
};
2.二分算法
可以根据目标值来划分区间，具有二段性。[0, ret] 之间的元素，平⽅之后都是⼩于等于 x 的，ret可能为目标值，令left=ret；[ret + 1, x] 之间的元素，平⽅之后都是⼤于 x 的，令right=ret-1。
如果按小于x和大于等于x的区间来划分同理，分别令left=mid+1和right=mid即可
class Solution
{
public:
int mySqrt(int x)
{
if(x < 1) return 0; // 处理边界情况
int left = 1, right = x;
while(left < right)
{
long long mid = left + (right - left + 1) / 2; // 防溢出
if(mid * mid <= x) left = mid;
else right = mid - 1;
}
return left;
}
};
4. (35.) 搜索插⼊位置
4.1算法原理
设插入位置为ret，根据题意分析二段性可划分为小于目标值t和大于等于t的区域，左右指针的移动情况如下，当mid落在[left,ret-1]区域时由于全部小于t，令left=mid+1;当mid落在[ret,right】中时由于ret可能为目标值所以令right=mid
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int left=0,right=nums.size()-1;
while(left<right)
{
int mid=left+(right-left)/2;
if(nums[mid]<target) left=mid+1;
else right=mid;
}
//判断目标值大于数组中最大元素的情况，根据题意要返回下一位索引
if(target>nums[right]) return right+1;
return left;
//由于左右指针已经相遇，返回谁都可以
}
};
5. (852.) ⼭脉数组的峰顶索引
5.1算法原理
- 1.暴力解法
峰顶的特点：⽐两侧的元素都要⼤。因此，我们可以遍历数组内的每⼀个元素，找到某⼀个元素⽐两边的元素⼤即可
class Solution {
public:
int peakIndexInMountainArray(vector<int>& arr) {
int n = arr.size();
// 遍历数组内每⼀个元素，直到找到峰顶
for (int i = 1; i < n - 1; i++)
// 峰顶满⾜的条件
if (arr[i] > arr[i - 1] && arr[i] > arr[i + 1])
return i;
// 为了处理 oj 需要控制所有路径都有返回值
return -1;
}
};
- 2.二分查找
虽然该题数组不有序，但具有二段性，山峰左右两边都小于山峰值，中间位置mid可以分为以下两种种情况：
1.用索引mid和mid-1进行比较
峰值mid一定得放到左边区间中，因为是和前一个元素作比较，左区间中的最后一个元素可能位峰值，若放到右边区间中更新索引时峰值可能会被跳过，mid的计算要+1
class Solution {
public:
int peakIndexInMountainArray(vector<int>& arr) {
int left=1,right=arr.size()-2;
while(left<right)
{
int mid=left+(right-left+1)/2;
if(arr[mid]>arr[mid-1]) left=mid;
else right=mid-1;
}
return left;
}
};
2.用索引mid和mid+1作比较
此时将峰值放到右边区间，右边区间的第一个元素可能为峰值，更新时right=mid，left=mid+1，此时mid的计算不+1
class Solution {
public:
int peakIndexInMountainArray(vector<int>& arr) {
int left=1,right=arr.size()-2;
while(left<right)
{
int mid=left+(right-left)/2;
if(arr[mid+1]>arr[mid]) left=mid+1;
else right=mid;
}
return left;
}
};
6. (153.) 寻找旋转排序数组中的最⼩值
6.1算法原理
由题意得数组升序，旋转后具有两段性
旋转后的数据分为这样两段，C点即为所求最小值。我们以D点作为划分值
当mid落在AB区间时不满足，left=mid+1要跳出该区间；落在CD区间时mid<=最小值，为了缩小搜寻范围令right=mid
class Solution {
public:
int findMin(vector<int>& nums) {
int n=nums.size()-1;
int left=0,right=n;
while(left<right)
{
int mid=left+(right-left)/2;
if(nums[mid]>nums[n]) left=mid+1;
if(nums[mid]<=nums[n]) right=mid;
}
return nums[right];
}
};
7. (173.)点名
7.1算法原理
二分查找
由题意得数组递增且有序,中间会少一个数,这个数就可以把数组划分为两个区间
前区间元素值对应索引,后区间元素对应索引+1,我们要求的就是后区间的第一个元素
细节问题:
若数组未被划分为两个区间,每个元素都等于其索引,那缺失值超出数组索引有效范围,返回最后索引+1
class Solution {
public:
int takeAttendance(vector<int>& records) {
int left=0,right=records.size()-1;
while(left<right)
{
int mid=left+(right-left)/2;
if(records[mid]==mid) left=mid+1;
else right=mid;
}
//完全连续的特殊情况判断
if(records[right]==right) return right+1;
else return right;
}
};
除此之外还可以尝试
1.哈希表
2.直接遍历找结果
3.位运算
4.数学(高斯求和公式)
这些方法的时间复杂度都为O(n),不如二分