查算法：⼆分查（1，0）问题模型（0，1）问题模型、三分查
查是指在数据集合中寻满⾜某种条件的数据元素的过程，⽤于查的数据集合则成为查表，查表中的数据元素类型是⼀致的，并且有能够唯⼀标识出元素的关键字。如果从查表出了关键字等于某⼀个给定值的数据元素，则称为查成功，否则称查不成功。 静态查表：对查表只进⾏（查和检索）
静态查表建⽴之后，不能再执⾏插⼊或者是删除的操作，查表页不再发⽣变化。对应的，如果对查表还需要执⾏两种操作，那么这类查表就是动态查表。
动态查表：（查、检索、插⼊、删除）
⽽对于动态查表，往往使⽤⼆叉平衡树、B-树或者哈希表来处理
对于各种各样的查算法， 我们⽤平均查长度来衡量查算法的性能，对于含有n个元素的查表，定义查成功的平均查长度为ASL = （加和）PiCi
Pi是搜索查表中第i个记录的概率，并且概率的加和是1
Ci是搜索查表中的第i个元素时直到查成功为⽌，表中元素的⽐较次数，考虑到查不成功的情况。
查算法的平均查长度应该是查成功的平均查长度和查不成功的平均查长度之和。
在后⾯的课程中，我们会继续巩固平均查长度的概念，并且会给同学们介绍顺序查、折半查和分块查。
⼆分查
1. min = 0, max = 尾巴指针, mid中间指针
2. 终⽌条件(min >= max)
3. 如果arr[mid] < x ----min = mid + 1;
4. arr[mid] > x ---- max = mid - 1;
5. arr[mid] == x ---- 到结果
⼆分查会出现， 跳跃个不停，不能得出结果的情况吗？
工程图纸尺寸111110000 要查最后那个1
我们把1看作是满⾜问题条件，0看作是不满⾜条件；
因此我们把问题模型抽象化为
1. min = 0, max是尾指针；mid = （min + max） / 2
2. arr[mid] == 1, min = mid (不能往后+1，因为不知道这个1是不是最后⼀个1啊）
3. arr[mid] != 1, max = mid - 1（可以往左看⼀个，因为这个max == mid 肯定不是满⾜性质的）
4. min == max，就到结果
但是不是如此就结束了，加⼊，我现在区间是0000000
上⾯的操作还能顺利到1吗？
高级律师
显然此时我的min == max，也不能指向我希望的数字，我现在可以默认min = -1，这样不断靠近，最后靠近到-1，才能说明我没有到啊，
万盛区委书记//11111111111000000000000
int binary_search(int*arr,int n){
int head =0, tail = n -1, mid;
while(head <= tail){
cout <<"head = "<< head <<", tail = "<< tail << endl;
mid =(head + tail +1)>>1;
爱心预支if(arr[mid]==0) tail = mid -1;
else head = mid;
if(head == tail)return(arr[head]==1? head :-1);
}
// return (arr[head] == 1 ? head : -1);
}
0000111111，最前⾯的⼀个1
相当于到⼀个最先满⾜条件的值的下标
当前我需要调整和思考的问题是，min是头指针，max是尾指针，mid = (min + max) / 2;
1. 如果arr[mid] == 1, min
顺序查
1. 顺序查（线性查）
顺序查算法是最直观的⼀种查算法，从线性表的⼀段出发，逐个⽐较。
顺序查分为：对⼀般的⽆序线性表的顺序查和对按关键字有序的线性表的顺序查。
2. 相对于⽆序查表，有序查表可以降低（查不成功情况下的检索次数）
例⼦：开辟⼀个动态的数组，存放数字
折半查
1. 折半查的时间复杂度稳定为O(logn)
2. 折半查只能应⽤在有序的顺序表中，因为链表不能够随机访问元素，所以折半查不能直接应⽤在链表中
3. 折半查中，中点选择不同的 会导致⼆叉判定树的形态发⽣变化，但是时间复杂度不会改变
int search(int*data,int length,int value){
int ans =0;
int l =0, r = length -1;
while(l <= r){
int mid =(l + r)/2;
ans++;
if(data[mid]== value){
printf("%d success\n", ans);
return0;
}else if(data[mid]> value){
r = mid -1;
}else if(data[mid]< value){
l = mid +1;
}
}
printf("%d failed\n", ans);
return0;
}
三分查
凹凸函数求极值点的问题：例⼦
1. ⾸先把区间[L, R]平均分成三部分：
m1三分点，m2三分点
magma铸造模拟软件2. 计算三等分点m1和m2对应的函数值
3. ⽐较两个函数值的⼤⼩，救国论坛
⾸先，循环终⽌条件是right - left < 2，⽽且这时候两者之间只有left left + 1两个元素了
我们让m1 是left + (right -left) / 3
m2是right-(right - left + 2)/ 3，这也就是说尽量让m2往极点靠拢
分块查
分块查也被叫做索引顺序查，在分块查⽅法中，我们需要建⽴⼀个索引表，索引表包含两类信息：关键字和指针其中，关键字指的是厄秘⼀个⼦表中最⼤的关键字，指针则表⽰这个⼦表中第⼀个元素在整个表中的下标
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议