二分查找算法描述如下:intsearch_bin(sst st, kt key){ low=1 ; high=st. length;
时间: 2023-05-17 20:00:40 浏览: 316
二分查找算法
二分查找算法也被称为折半查找算法,是一种常见的查找算法。其主要思想是在有序数组中查找某个元素时,先确定该元素在数组中可能出现的区间范围,然后每次取该范围的中间值与目标元素进行比较,不断缩小目标元素可能出现的范围。当目标元素与中间值相等时,查找成功,否则根据中间值与目标元素的大小关系调整区间范围,再进行下一次查找。
具体地,二分查找算法的描述如下:
输入:已经有序的数组sst,待查找的元素kt
输出:目标元素的下标或者-1(表示未找到)
1. 初始化low=1,high为数组长度
2. 当low<=high时,重复以下步骤:
- a. 取中间值mid=(low+high)/2
- b. 若中间值等于目标元素kt,则返回mid
- c. 若中间值大于目标元素kt,则缩小右边的区间范围,将high=mid-1
- d. 若中间值小于目标元素kt,则缩小左边的区间范围,将low=mid+1
3. 若未找到目标元素,则返回-1
二分查找算法的时间复杂度为O(logn),相比于线性查找算法具有更高的效率。同时,该算法只适用于有序数组,对于无序数组需要先进行排序操作。
阅读全文