二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。
二分查找法是已经排好顺序的集合，要从集合的中间开始查找，如果这个项小于我们要查找的数，则这个项前边的所有数都小于我们要查找的对象
就无需再浪费时间去查在前边的数查找;如果搜寻的数天于我们要查找的对象那么这个数的后边的数都大于我们要查找的对象，则后边的数我们也不用再去查找了。
下边我会用c#和c++两种语言给出代码
c#二分查找代码
static
void
Main(
string
[] args)
{
int
[] _array={ 1,3,5,6,10,14,16,20,21,23,28};
int
_findValue = BinSearch(_array, 0, _array.Length, 3);
if
(_findValue == -1)
{
Console.WriteLine(
"not find"
);
}
else
{
Console.WriteLine(
"find the value at "
+ _findValue);
}
Console.ReadLine();
}
static
int
BinSearch(
int
[] _array,
int
start,
int
end,
int
key)
{
int
left, right;
int
mid;
left = start;
right = end;
while
(left <= right)
{
mid = (left + right) / 2;
if
(key < _array[mid])
{
right = mid - 1;
}
else
if
(key > _array[mid])
{
left = mid + 1;
}
else
return
mid;
}
return
-1;
}
|
c++二分查找代码
int
BinSearch(
const
int
* Array,
int
start,
int
end,
int
key)
{
int
left,right;
int
mid;
left=start;
right=end;
while
(left<=right)
{
mid = (left + right)/2;
if
(key < Array[mid])
{
right = mid - 1;
}
else
if
(key > Array[mid])
{
left = mid + 1;
}
else
return
mid;
}
return
-1;
}
int
main(
int
argc,
char
* argv[])
{
int
_array[11] ={ 1,3,5,6,10,14,16,20,21,23,28};
int
_findInt =BinSearch( _array,0,(
sizeof
_array)/(
sizeof
_array[0]),3);
if
(_findInt == -1)
{
cout<<
"not find"
<<endl;
}
else
{
cout<<
"find the Value at "
<<_findInt<<endl;
}
return
0;
}
|
本文转自lpxxn博客园博客，原文链接：http://www.cnblogs.com/li-peng/p/3300894.html，如需转载请自行联系原作者
