数据结构、刷leetcode返航版--二分【有序】5/7

1.排序

快排：

第一章基础算法（一） - AcWing

如何调整范围

经典二分

递归结束条件；条件满足时，进行处理；递归左边，递归右边

分界点划分可以是l,r,(l+r)/2,但是如果是选l，比如是1,2排序，i最后结束循环是1，然后最后递归也是sort(q,0,0)

其实有太多问题：>=和>的选择，要不要判断i<j，递归使用i,i-1还是j,j+1【前一个超时了】，先这样吧，想不通。。。。。？？？？？

模版：

void sort(vector<int>&nums,int l,int r){//感觉情况有点多啊
if(l>=r){
return;
}
int i = l-1;
int j = r+1;
int x = nums[(l+r)/2];
while(i<j){
do{
i++;
}while(nums[i]<x);//不是<=,如果=x应该让他放在中间
do{
j--;
} while(nums[j]>x);//不是<=
if(i<j) swap(nums[i],nums[j]);//必须i<j
}//i>=j j,i
sort(nums,l,i-1);
sort(nums,i,r);
}

#include<iostream>
#include<algorithm>
using namespace std;// 5
// 3 1 2 4 5
//
// void sort(vector<int>&nums,int l,int r){//二分
//     if(l>=r){
//         return;
//     }//     int i = l;
//     int j = r;//两个指针
//     int x = nums[(l+r)/2];//避免死循环
//     cout<<"I:"<<i<<"j:"<<j<<endl<<"x"<<x;
//     while(i<j){//
//         while(nums[i]<=x){
//             i++;// 可能导致 i 越界
//         }
//         while(nums[j]>=x){
//             j--;// 可能导致 j 越界
//         }
//         swap(nums[i],nums[j]);// 交换后未移动指针
//     }//结束：i>=j
//     sort(nums,l,i-1);
//     sort(nums,i,r);// }
void sort(vector<int>&nums,int l,int r){//感觉情况有点多啊if(l>=r){return;}int i = l-1;int j = r+1;int x = nums[(l+r)/2];while(i<j){do{i++;}while(nums[i]<x);//不是<=,如果=x应该让他放在中间// do { i++; } while (nums[i] < x); do{j--;} while(nums[j]>x);//不是<=if(i<j) swap(nums[i],nums[j]);//必须i<j}//i>=j j,isort(nums,l,i-1);sort(nums,i,r);
}int main(){int num;cin>>num;vector<int>vec(num);for(int i=0;i<num;i++){cin>>vec[i];// cout<<vec[i];}sort(vec,0,num-1);//num-1for(int s:vec){cout<<s<<" ";}
}

冒泡排序：
每一次把max数放到最后一位

void bubble_sort(int q[], int n) {
bool flag = true;
while (flag) {
flag = false;
for (int i = 1; i < n; i++) {
if (q[i] > q[i + 1]) {
flag = true;
int t = q[i];
q[i] = q[i + 1];
q[i + 1] = t;
}
}
}
}

2、搜索插入位置【实际1h+】

刷题论 04｜二分查找，你根本不需要背那么多模板_哔哩哔哩_bilibili

35. 搜索插入位置 - 力扣（LeetCode）

~~迷茫了5/7~~

---------------------------------------------

需要注意最好(l+r)/2用l+((r-l)>>2)代替，防止溢出

最优思路：刚开始没想到可以只是先找target，找不到位置就是l【自己举例子】

int findIndex1(vector<int>& nums, int l, int r, int target) {

if (l > r) {//[l,r]大于和大于等于【1,3,5,6,target= 7,l>=r返回的是3而非4】，如果用【1，r】理论看的话，l是可以等于r的，没必要返回循环

return l;

}

int m = l + ((r - l) >>2);

if (nums[m] == target) {

return m;

} else if (nums[m] < target) {

return findIndex1(nums, m + 1, r, target);

} else {

return findIndex1(nums, l, m - 1, target);

}

}

原来的想法是在每次二分查找中如果找不到target，直接找到一侧小一侧大的那个位置，然后就不知道循环结束条件是什么了，确实也不需要了，不过自己考虑时问题挺多

考虑成了m-1小于target而m+1大于target【应该是m】

0前面插入和nums.size()-1后面插入的逻辑没考虑清楚

int findIndex(vector<int>& nums, int l, int r, int target) {// if (l > r) {// 当 l > r 时，说明 target 应插入到 l 的位置//    return l;}
//int m = l + (r - l) / 2;if (nums[m] == target) {return m; // 直接找到目标}// 检查是否满足插入条件：nums[m-1] < target < nums[m]if (m > 0 && nums[m-1] < target && nums[m] > target) {return m; // 插入到 m 的位置}// 处理边界情况（如插入到数组最左或最右）if (m == 0 && nums[m] > target) return 0;if (m == nums.size() - 1 && nums[m] < target) return m + 1;// 递归搜索左半部分或右半部分if (nums[m] < target) {return findIndex(nums, m + 1, r, target);} else {return findIndex(nums, l, m - 1, target);}}

模版：简单二分，数组中不包含重复元素，思考：定义是[l,r]闭区间，跳出循环条件:l > r，l / r = mid +-1;