问题描述：

改写二分查找算法：设a[1…n]是一个已经排好序的数组，改写二分查找算法:

1. 当搜索元素x不在数组中时，返回小于x的最大元素位置i，和大于x的最小元素位置j； (即返回x的左、右2个元素)

2. 当搜索元素x在数组中时，i和j相同，均为x在数组中的位置；

3. 并计算其时间复杂度？

代码如下：

# -*- coding: utf-8 -*-
"""
Created on Tue Oct 11 09:07:23 2022@author: Dell
"""
def BSearch(ary, left, right, result) :if result < ary[0] :print('小于最小值',ary[0])return -1if result > ary[right]:print('大于最大值',ary[right])return -1while left <= right :mid = int((left+right)/2)if ary[mid]==result :print('x的元素位置i为',mid, ' 值为：', ary[mid])breakelse :if ary[mid]<result:left = mid + 1if ary[left] > result :print('小于x的最大元素位置i为',left-1, ' 值为：', ary[left-1])print('大于x的最小元素位置j为',left, ' 值为：', ary[left])breakif ary[mid]>result:right = mid - 1if ary[right] < result :print('大于x的最小元素位置j为',right + 1, ' 值为：', ary[right+1])print('小于x的最大元素位置i为',right, ' 值为：', ary[right])breakreturn -1if __name__=='__main__':input_list = [1, 2, 5, 8, 9, 13, 17, 28, 32, 36, 41]left = 0right = len(input_list) - 1result = 15BSearch(input_list, left, right, result)

第一次二分后，在n/2个元素中查找；
第二次二分后，在n/2^2 个元素中查找；

设t为查找次数，最坏情况下，只剩下一个元素，即n/2^t =1，那么t = log2⁡(n)，
所以时间复杂度为O(log2(⁡n))