百科知识

算法设计​算法设计5.3 给定一个有序数组A1...n-,以及

2018-03-31 05:19:07肆***
算法设计5.3 给定一个有序数组A[1...n],以及一个元素x,设计一个寻找x的分治算法并分析其时间复杂度,要求返回x在数组中的位置算法设计​算法设计5.3 给定一个有序数组A[1...n],以及一个元素x,设计一个寻找x的分治算法并分析其时间复杂度,要求返回x在数组中的位置:既然是有序数组?

最佳回答

  • 既然是有序数组,肯定采用二分法,先判断n/2的元素和x的大小对比,一次查找就能确定是在哪个区域,如果从小到大,A[n/2] 如果大于x,就能判断在后半段区间,只需要查找后半段,然后重复这种查找,就能很快锁定x位置,这种查找方法每次缩小1/2(第二次缩小原始的1/4,这里的1/2说的是缩小范围后的范围)查找范围,效率很高
    2018-03-31 06:41:17
  • 很赞哦! (259)