二分查找也叫折半查找,它只对有序的序列有效。二叉查找的基本步骤是:
int binarySearch(const int *arr, int array_size, int key)
{
int low = 0, high = array_size - 1, mid;
while (low <= high)
{
mid = (low + high) / 2;
if (arr[mid] == key)
return mid;
if (arr[mid] > key)
high = mid - 1;
else
low = mid + 1;
}
return -1;
}
遍历查找的时间复杂度是O(n),二分查找则是O(logn)。因此在有序序列上,使用二分查找的效率比较高。