二分搜索的基本相关问题
二分搜索的基本相关问题
二分查找是基于分治思想的一种算法，所谓分治思想就是将一些规模很大难于直接解决的问题，缩小为一个较小的问题就很容易解决的思想，（当然它的子问题仍可以继续分解为相同的子问题）。归结为一句话就是：“以大化小，各个击破，分而治之，组合取果”。
二分查找作为一种高效的查找算法，是解决一些有序序列查找的不二之选。但他的缺点也就是使用于有序的数组，有一定的局限性。但二分在一些高效的程序设计中往往被用作优化的利器。因此，熟练应用二分查找是必须的。
二分查找的实现：比如有一列数从 1 到 100 ，已经排好序，我们要查找 25 ，按照传统的逐个遍历，需要查找 25 次，而采用二分查找的方法，首先那 25 和这组数列的中间的数做比较 50 ，结果查找数小于中间数，所以区间【 50-100 】的数就可以舍弃了，然后查找范围就缩减为了【 1-49 】，接下来仍然那 25 和查找区间的中间数 25 做比较，显然这样已经查找到了，这样只需要 2 次就查找到了，而普通的查找方法需要 25 次。
假设其数组长度为n，其算法复杂度为o（log（n）），灰常高效。
【二分算法的非递归实现】
这个可能就是 C++ 中 STL 库中的那个。
1 int BinarySearch( int a[], int n, int x) // a[]待查找数组 n查找范围 x被查找数
2 {
3 int low= 0 ; // 查找区间 起点
4 int high=n- 1 ; // 查找区间 终点
5 while (low<= high)
6 {
7 int mid=(low+high)/ 2 ;
8 if (x==a[mid]) // 如果查找成功 返回其下标
9 return mid;
10 else if (x> a[mid])
11 low=mid+ 1 ;
12 else if (x< a[mid])
13 high=mid- 1 ;
14 }
15 return - 1 ; // 查找失败
16 }
【STL中的binary_search】
当然，如果是纯粹的二分搜索，可以直接调用algorithm 中的二分搜索函数，上面的就都省了。、
强大的C++标准模板库中提供有二分查找函数，直接调用可以节省时间：
binary_search(num,num+n,key);
这里的参数num指查找序列（已经排过序），num-num+n指查找范围，key指待查找的值。
如果查找成功则返回true，否则返回false。
【二分搜索的递归实现】
1 int BinarySearch( int a[], int x, int low, int high) // a[]待查找数组 low/high查找范围 x被查找数
2 {
3 if (low>high) return - 1 ;
4
5 int mid=(low+high)/ 2 ;
6 if (x==a[mid]) // 如果查找成功 返回其下标
7 return mid;
8 else if (x> a[mid])
9 BinarySearch(a,x,mid+ 1 ,high);
10 else if (x< a[mid])
11 BinarySearch(a,x,low,mid- 1 );
12
13 }
二分作为一种基本的算法，在程序设计题中往往不会单独用到，而更像是一种工具，常用作一些问题的优化。
标签: 二分查找
作者： Leo_wl
出处： http://www.cnblogs.com/Leo_wl/
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。
版权信息