php电商网站开发流程图,做网站 合肥,仿淘宝网站源码+php,大连建设工程网站一、查找精确值
从一个有序数组中找到一个符合要求的精确值#xff08;如猜数游戏#xff09;。如查找值为Key的元素下标#xff0c;不存在返回-1。
//这里是leftright。
//考虑这种情况#xff1a;如果最后剩下A[i]和A[i1]#xff08;这也是最容易导致导致死循环的…一、查找精确值
从一个有序数组中找到一个符合要求的精确值如猜数游戏。如查找值为Key的元素下标不存在返回-1。
//这里是leftright。
//考虑这种情况如果最后剩下A[i]和A[i1]这也是最容易导致导致死循环的情况)首先mid i,
//如果A[mid] key那么left mid1 i 1如果是小于号则A[i 1]不会被检查导致错误
int left 1,right n;
while(left right)
{//这里left和right代表的是数组下标所有没有必要改写成mid left (right - left)/2;//因为当代表数组下标的时候在数值越界之前内存可能就已经越界了//如果left和right代表的是一个整数就有必要使用后面一种写法防止整数越界int mid (left right) / 2;if(A[mid] key)return mid;else if(A[mid] key)//这里因为mid不可能是答案了所以搜索范围都需要将mid排除right mid - 1;elseleft mid 1;
}
return -1;二、查找大于等于/大于key的第一个元素
这种通常题目描述为满足某种情况的最小的元素。
int left 1,right n;
while(left right)
{//这里不需要加1。我们考虑如下的情况最后只剩下A[i],A[i 1]。//首先mid i如果A[mid] key那么right left i跳出循环如果A[mid] keyleft right i 1跳出循环所有不会死循环。int mid (left right) / 2;if(A[mid] key)//如果要求大于等于可以加上等于也可以是check(A[mid])right mid;//因为找的是大于key的第一个元素那么比A[mid]大的元素肯定不是第一个大于key的元素因为A[mid]已经大于key了所以把mid1到后面的排除elseleft mid 1;//如果A[mid]小于key的话那么A[mid]以及比A[mid]小的数都需要排除因为他们都小于key。不可能是第一个大于等于key的元素
}三、查找小于等于/小于key的最后一个元素
这种通常题目描述为满足某种情况的最大的元素。如Leetcode69题求sqrt(x)向下取整就是这种模板。
int left 1, right n;
while(left right)
{//这里mid (left right 1) / 2;//考虑如下一种情况最后只剩下A[i],A[i 1]如果不加1那么mid i如果A[mid] key执行更新操作后left midright mid 1就会是死循环。//加上1后mid i 1,如果A[mid] key那么left right mid 1,跳出循环。如果A[mid] keyleft mid i跳出循环。int mid (left right 1) / 2;if(A[mid] key)left mid;//如果A[mid]小于key说明比A[mid]更小的数肯定不是小于key的最大的元素了所以要排除mid之前的所有元素elseright mid - 1;//如果A[mid]大于key那么说明A[mid]以及比A[mid]还要大的数都不可能小于key所以排除A[mid]及其之后的元素。
}四、总结
最后两种情况的循环跳出条件是leftright为什么不是小于等于呢因为我们的区间变换思路是不断的舍去不可能是解的区间最后只剩下一个数就是我们的解。而第一种情况就算最后只剩一个数也有可能不是解所以需要使用小于等于。
查找精确值循环条件是小于等于查找满足情况的最大最小值循环条件是小于。查找满足条件的最大数mid (right left 1) / 2查找满足条件的最小数mid (right left)/2mid left (right - left) / 2不是适用于所有的情况。如果存在没有解的情况比如从[1,2,3,4,5]找出大于等于6的第一个数我们只需要将最后剩下的数单独进行一次判断就可以了。
作者T-SHLoRk 链接https://www.acwing.com/blog/content/307/ 来源AcWing 著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。
