二分(折半)查找
程序员文章站
2022-03-14 20:35:14
...
前提条件:
List——一个元素有序存放的线性列表;
k——待查找的元素。
二分查找法的原理是:这里假设List是按照递增顺序排列,对于给定的关键字k,比较k和处于List的中间位置的元素的大小关系,根据这个大小关系来确定k是在List的中间还是在List的前半段或后半段,以此类推,知道找到元素k或者查找失败。
C++实现:
/*----------------------------------------
Array是存储待查找元素的数组
length是数组的长度或者说是待查找序列的元素个数
item是待查找的元素
----------------------------------------*/
void binarySearch(int* Array, int length, int item) {
if (Array == NULL)
return;
int first = 0,
last = length - 1,
mid;
bool found = 0;
while (first <= last && found == false) {
mid = (first + last) / 2;
if (item > Array[mid]) {
first = mid + 1;
}
else if (item < Array[mid]) {
last = mid - 1;
}
else if(item == Array[mid]) {
cout << mid << endl;//输出item在Array中的索引号(以0开始)
found = true;
}
}
}