数据结构与算法分析

算法

折半查找算法

目标：对一个有序列表进行折半查找。

前置条件；列表元素按照升序排列并被存储在一个数组a中。这个列表具有n个元素，这里n是一个正整数。Item是被查找的值，它的类型和数组元素的类型相同。

后置条件：如果查找成功，found为真，而mid是item在数组中的位置；否则，found为假。

void binarySearch(NumberArray a, ElementType item, bool &found, int &mid)

{

int first = 0, //当前被搜索的子列表的第一个和最后一个位置

last= n - 1;

found = false;

while(first <= last && !found)

{

mid= (first + last) / 2;

if(item < a[mid])

{

last = mid - 1;

}

else if (item > a[mid])

{

first = mid + 1;

}

else

{

found = true;

}

}

}