用二分查找在已排序的数组中查看该数组是否含有一个特定的值是非常快速的,时间复杂度为O(lgn). 二分查找思想很简单,但是实现的时候会在边界条件上出现一些意想不到的问题。 现贴出自己写的程序,供大家参考。
第一个实现是基于迭代方式:
/// <summary>
/// implement Binary Search algorithm through iteration approach.
/// </summary>
/// <param name="array">a sorted array</param>
/// <param name="key">key value </param>
/// <returns>the position of the key in the array. If this key is not found, return -1</returns>
public int BinarySearchIteration(int[] array, int key)
{
int begin = 0;
int end = array.Length - 1;
while (begin <= end)
{
int mid = begin + (end - begin) / 2;
if (array[mid] > key)
{
end = mid - 1;
}
else if (array[mid] < key)
{
begin = mid + 1;
}
else
{
return mid;
}
}
return -1;
}
下一个是基于递归方式实现:
/// <summary>
/// implement Binary Search algorithm through recursion approach.
/// </summary>
/// <param name="array">a sorted array</param>
/// <param name="begin">the search starting position</param>
/// <param name="end">the search finishing position</param>
/// <param name="key">the key value</param>
/// <returns>the position of the key in the array. If this key is not found, return -1</returns>
public int BinaraySearchRecursive(int[] array, int begin, int end, int key)
{
if (begin <= end)
{
int mid = begin + (end - begin) / 2;
if (array[mid] > key)
{
return BinaraySearchRecursive(array, begin, mid - 1, key);
}
else if (array[mid] < key)
{
return BinaraySearchRecursive(array, mid + 1, end, key);
}
else
{
return mid;
}
}
else
{
return -1;
}
}
这里应该注意两个地方:
一是对于mid 的值,应该用代码中的方式获得,不能通过 mid = (begin + end) /2 来取得,因为 begin + end 的值会有可能大于 int 的最大值。
二是要注意在 if 判断的时候用 <=, 没有必要用 <, 然后再去做判断,否则会多此一举,而且也让代码显得很难看。
参考文献:
1.http://www.zhuoda.org/weiking/67932.html
2.http://www.cppblog.com/converse/archive/2009/02/28/75190.html
分享到:
相关推荐
安徽大学本科课程《算法设计与分析》实验二《二分查找算法BinarySearch》,包括.m文件和实验报告。
下面是一个简单的 Python 实现二分查找算法的示例: ```python def binary_search(arr, target): left = 0 right = len(arr) - 1 while left mid = (left + right) // 2 if arr[mid] == target: return ...
amoeba-mysql-binary-2.2.0.tar.gz amoeba-mysql-binary-2.2.0.tar.gz amoeba-mysql-binary-2.2.0.tar.gz amoeba-mysql-binary-2.2.0.tar.gzamoeba-mysql-binary-2.2.0.tar.gz amoeba-mysql-binary-2.2.0.tar.gz ...
基于python的查找算法-二分查找Binary Search
c++ 二分搜索树 二分查找树 binary search tree BST
//二分查找,递归实现 int binarySearch(int a[],int low,int high,int key) { //查找某元素是否在数组中,若存在,则返回下标,否则返回-1; int mid=(low+high)/2; if(low>high){ return -1;//该元素不...
描述: ...第二行为n(n不超过10000)个整数;第三行为一个整数m(m不超过50000),表示查询的个数;接下来m行每行一个整数k。 输出: 每个查询的输出占一行,如果k在序列中,输出Yes,否则输出No。
C 语言中效率最高的查找方式,非常实用。...函数功能: 二分查找 入口参数: 待查找有序表的首地址 int *a 待查找的数据 int num 出口参数: 查找成功返回数据在有序表中的位置0 ~ n-1,不成功返回 -1
折半查找,也称为二分查找(Binary Search)或对数查找(Logarithmic Search),是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束;...
二分查找Binary.java
二分查找
AjaxControlToolkit.Binary.NET4AjaxControlToolkit.Binary.NET4AjaxControlToolkit.Binary.NET4AjaxControlToolkit.Binary.NET4AjaxControlToolkit.Binary.NET4AjaxControlToolkit.Binary.NET4AjaxControlToolkit....
cef_binary_3.2623.1401.gb90a3be_windows32.7z cef_binary_3.2623.1401.gb90a3be_windows32.7z cef_binary_3.2623.1401.gb90a3be_windows32.7z
课本上的二分查找的实现。有初始化,赋值,搜索三个操作
A binary search algorithm (or binary chop) is a technique for finding a particular value in a sorted list. It makes progressively better guesses, and closes in on the sought value, by comparing an ...
比较在同一有序表下进行顺序查找和二分查找的效率 表中的奇数从1开始一共n个,要查找searches次。 1.生成新的有序表 2.测试顺序查找的效率" 3.测试binary-search1查找效率 4.测试binary-search2查找效率
二分查找Binary_Search套路和解题模板【LeetCode刷题套路教程3】
cef_binary_3.2623.1395.g3034273_windows32在WindowsXP编译的库文件和源码
cef_binary_3.1547.1412_windows32.7z 浏览器开发 加载webkit 可用于 二次开发
cef_binary_3.3029.1619.geeeb5d7_windows32 windows cef二进制文件包