自己做的网站 打开了没有图片,私域流量运营管理,计算机编程网课,新东家网站建设文章目录思路代码以二分区间作为while判定条件以给定值作为while判定条件主函数思路
while判定条件的选择#xff0c;注意最外层的return的内容就好。下面提供了两个代码版本。计算 mid 时需要防止溢出#xff08;对应类型【如本例中的int】可能存不下#xff09;#xff…
文章目录思路代码以二分区间作为while判定条件以给定值作为while判定条件主函数思路
while判定条件的选择注意最外层的return的内容就好。下面提供了两个代码版本。计算 mid 时需要防止溢出对应类型【如本例中的int】可能存不下即 midleft(right-left)/2。如何更改二分区间
重点说第三点一开始的选择是当num在mid左边时直接将mid给right反之num在mid右边将mid给left。但是这就出现了一个问题。例如
数组元素为 1 3 5 的时候如果你想要找4那么
第一次left 0 right 2 mid 1第二次left 1 right 2 mid left(right-left)/2 1。
可以看出mid指向的下标是没有更改的因此程序会陷入一直以下标1为left、mid以下标2为right的尴尬情况——死循环。如果只是单纯的将mid的值粗暴的赋给left或者right是没法解决问题的因为会在一个重复的区间不断查找——当mid所指向的数组元素不为num时mid位置已经可以被排除了其不应该作为下一次二分区间内的位置。
说人话就是当数组arr中有n个元素应如下图 这样的话就可以避免区间永远保持rightleft的尴尬情况此时也就可以通过将while的判定条件设置为left和right之间的关系来完成判定。
代码
以二分区间作为while判定条件
#include iostream
#include vectorusing namespace std;int halffind(vectorint vi, int num){int left 0;int right vi.size() - 1;while (left right) {int mid left (right - left)/2;int temp vi[mid];if(temp num){return mid;}if(temp num){left mid 1;}if(temp num){right mid - 1;}}return -1;
}以给定值作为while判定条件
int halffind(vectorint vi, int num){int left 0;int right vi.size() - 1;int mid left (right - left)/2;while (vi[mid] ! num) {int temp vi[mid];if(left right){return -1;}if(temp num){left mid 1;}if(temp num){right mid - 1;}mid left (right - left)/2;}return mid;
}主函数
int main(int argc, char const *argv[]) {vectorint ivec;int time,num;cout 数组元素个数 endl;cin time;cout 输入数组元素 endl;while (time--) {cin num;ivec.push_back(num);}int over;cout 想要寻找的数字 endl;cin over;if(halffind(ivec, over) ! -1){cout 下标为 halffind(ivec, over) endl;}else{cout 数字不在数组中 endl;}return 0;
}
