一道笔试题：用最快速度查出有序数组中的一个数

 用最快的方式从int[] arrayNum={3,5,9,12,27,33,44,96,102,122,202}中查出33在数组的哪一位？
大家想想有什么好的方法？

解决方案 »

  1.   

    有序的话使用二分查找法，时间复杂度是O(log n)
      

  2.   

    答:你没听过.我们可听过呵.
    1)Fibonacci查找的平均性能比二分查找好.只是在最坏情况下(时间复杂度仍是O(log n))比二分查找差.
    2)若数值平均分布大致线性时,插值查找平均性能也比二分查找好.
    因此,不要动不动就是二分查找.优秀程序员的责任是:根据数据或问题的特点,寻找尽可能优的方案.
      

  3.   

    1)Fibonacci查找的平均性能比二分查找好.只是在最坏情况下(时间复杂度仍是O(log n))比二分查找差. 学习了