设计一个算法,将元素x插入到一个有序(从小到大排序)顺序表的适当位置上, 并保持有序性。
时间: 2024-06-12 16:08:07 浏览: 68
在有序的顺序表的适当位置插入X
1. 初始化变量low=0, high=n-1,其中n为顺序表中元素的个数。
2. 当low<=high时,执行以下步骤:
a. 计算中间位置mid=(low+high)/2。
b. 如果x小于等于顺序表中下标为mid的元素,说明应该将x插入到low到mid之间,因此将high=mid-1。
c. 如果x大于顺序表中下标为mid的元素,说明应该将x插入到mid+1到high之间,因此将low=mid+1。
3. 将x插入到low位置上,即可保证顺序表的有序性。
时间复杂度为O(logn),因为每次将查找范围缩小一半。
阅读全文