概述二分查找的基础逻辑很简单:我们小时候都玩过猜数字游戏,心里想一个数字( 数字范围是 1-100),让对方猜,如果没猜对,就只告诉对方猜大了还是小了,看看最快几次能猜到。这个游戏的最佳策略就是二分。先猜 50,如果大了,就猜 25。这样最多 7 次就可以猜到答案。基础模版对于猜数字这个游戏来说,二分的模版最简单的就是如下形式:1234567891011121314151617// 二分查找intleft, right, mid, ans;left =1;right = n;ans =-1;while(left <= right) {mid = left + (right-left) /2;if(v[mid] > a) {right = mid -1;}elseif(v[mid] < a) {left = mid +1;}else{ans = mid;break;}}cout << ans <<" ";以上代码需要注意的有以下几点:查徇范围是[left, right],即 left 和 right 都是闭区间。循环条件是left <= right,即当left == right时,还需要进行一次测试。mid = left + (right-left) / 2其实等价于mid = (left + righ
...
继续阅读
(54)