First灬DKS
2015-01-03 15:27
采纳率: 0%
浏览 1.8k

这道题可以用折半查找的办法做吗?麻烦大神帮忙解答一下吧!!!谢谢!!!

有一个已经排好序的数组。现输入一个数,要求按原来的规律将它插入数组中, 插入之后依然有序。指针实现

  • 写回答
  • 好问题 提建议
  • 关注问题
  • 收藏
  • 邀请回答

6条回答 默认 最新

  • threenewbee 2015-01-03 15:43

    插入数组意味着需要将数组插入位置后面的元素全部搬动一次,相当低效。

    这里最好使用链表,当然更好的是使用二叉排序树。

    评论
    解决 无用
    打赏 举报
  • threenewbee 2015-01-03 15:44

    非要这么做也可以,参考

    http://blog.csdn.net/xiaofeige567/article/details/26879075

    文章是用的顺序查找,按照你说的折半查找也可以。

    评论
    解决 无用
    打赏 举报
  • Jason_White 2015-01-04 06:26

    已经有序了的,用二分法(就是你说的折半查找)速度是最快的,但是因为是数组,所以你的数组长度变化时内部的实现是比较耗时的,也不提倡这种做法。最好是用链表实现,或者list这些可以动态修改长度的结构。
    顺序查找的时间复杂度是f(x),二分法查找的时间复杂度是f(log2x),所以速度是最快的。

    评论
    解决 无用
    打赏 举报
  • 智者知已应修善业 2015-01-04 10:55
    评论
    解决 无用
    打赏 举报
  • 智者知已应修善业 2015-01-04 10:59
    评论
    解决 无用
    打赏 举报
  • 无规矩不成方圆 2015-01-05 12:31

    折半查找是一种查询已知的有序集合中有没有要找的元素,你的问题却要进行插入操作(本质是排序),问题不一样哦

    评论
    解决 无用
    打赏 举报

相关推荐 更多相似问题