首页 > 代码库 > 【从零学习经典算法系列】分治策略实例——二分查找
【从零学习经典算法系列】分治策略实例——二分查找
1、二分查找算法简介
二分查找算法是一种在有序数组中查找某一特定元素的搜索算法。搜素过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。如果在某一步骤数组 为空,则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。折半搜索每次把搜索区域减少一半,时间复杂度为Ο(logn)。
二分查找的优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难。因此,二分查找方法适用于不经常变动而查找频繁的有序列表。
2、二分查找算法要求
(1)必须采用顺序存储结构
(2)必须按关键字大小有序排列。
3、二分查找算法流程图
图1 二分查找算法流程图
4、c语言实现
#include <stdio.h> int binary_search_recursion(const int array[], int low, int high, int key) { int mid = low + (high - low)/2; if(low > high) return -1; else{ if(array[mid] == key) return mid; else if(array[mid] > key) return binary_search_recursion(array, low, mid-1, key); else return binary_search_recursion(array, mid+1, high, key); } } int binary_search_loop(const int array[], int len, int key) { int low = 0; int high = len - 1; int mid; while(low <= high){ mid = (low+high) / 2; if(array[mid] == key) return mid; else if(array[mid] > key) high = mid - 1; else low = mid + 1; } return -1; } int main() { const int num_array[] = {2,4,6,8,10,12,14,16,18,20}; int key; int key_pos; int array_size = sizeof(num_array)/sizeof(int); for(int i=0;i<array_size;i++){ printf("%d ",num_array[i]); if(i % 5 == 0) printf("\n"); } printf("\n"); while(1){ printf("Put in the number you want to find:\n"); scanf("%d",&key); //key_pos = binary_search_recursion(num_array, 0, array_size, key); key_pos = binary_search_loop(num_array, array_size, key); printf("The position of key is %d\n", key_pos); } }
图2 程序结果
5、造成边界错误的原因
二分查找算法的边界一般分为两种情况,一种为左闭右开区间,如[low,high),一种是左闭右闭区间,如[low,high]。这里需要注意的是循环体外的初始化条件,与循环体内的迭代步骤,都必须遵守一致的区间规则,也就是说,如果循环体初始化时,是以左闭右开区间为边界的,那么循环体内部的迭代也应该如此。
转载请注明作者与文章出处:http://blog.csdn.net/jasonding1354/article/details/38176171
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。