二分查找要求待查表为有序表。假设表中元素按升序排列，查找关键字时，首先将表中间位置记录的关键字与查找的关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录。

输入：数组A[1…n]与目标值T；输出：数组A中与T相等元素的下标。

①low = 1, high = n;

②while (low <= high) do

③——mid = (low + high)/2;

④——if A[mid] = T then

⑤————return mid;

⑥——else if A[mid] < T then

⑦————high = mid - 1;

⑧——else

⑨————low = mid + 1;

⑩return 0. \\未找到指定元素

用二分查找搜索47

二分查找效率很高，在长度为n的表中时间复杂度为O(log₂n)。但是，此算法只能应用于有序表中，无法在无序表中进行查找。