现在的位置: 主页 > 在线留言 > 文章列表

算法----二分查找算法

作者:北京夜明珠节能科技有限公司 来源:www.ymzjn.com 发布时间:2017-09-02 11:42:39
算法----二分查找算法

二分查找算法是在有序数组中用到的较为频繁的一种算法,在未接触二分查找算法时,最通用的一种做法是,对数组进行遍历,跟每个元素进行比较,其时间为O(n).但二分查找算法则更优,因为其查找时间为O(lgn),譬如数组{1, 2, 3, 4, 5, 6, 7, 8, 9},查找元素6,用二分查找的算法执行的话,其顺序为:
1.第一步查找中间元素,即5,由于5<6,则6必然在5之后的数组元素中,那么就在{6, 7, 8, 9}中查找,
2.寻找{6, 7, 8, 9}的中位数,为7,7>6,则6应该在7左边的数组元素中,那么只剩下6,即找到了。

二分查找算法就是不断将数组进行对半分割,每次拿中间元素和要查找的目标进行比较。

#include #include using namespace std; int binary_search(vector &vec, int value) { size_t len = vec.size(); int start = 0; int end = len-1; while (start <= end) { int mid = (end + start) / 2; if (vec[mid] == value) return mid; else if (vec[mid] > value) end = mid - 1; else start = mid + 1; } return -1; } int main(int argc, char*argv[]) { int idx = 0; vector vec = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; idx=binary_search(vec, 6); cout << idx << endl; return 0; }

php代码:

function binsearch($x,$a){ $c=count($a); $lower=0; $high=$c-1; while($lower<=$high){ $middle=intval(($lower+$high)/2); if($a[$middle]>$x) $high=$middle-1; elseif($a[$middle]<$x) $lower=$middle+1; else return $middle; } return -1; }

企业建站2800元起,携手武汉肥猫科技,做一个有见地的颜值派!更多优惠请戳:咸宁网站建设 http://xianning.45qun.com

上一篇:卡汀财经—CFA (特许金融分析师)简介 下一篇:最后一页