黑马程序员技术交流社区

标题: 关于数组折半查找的练习不同的思路，不知可行性如何？ [打印本页]
作者: 路边小色狼    时间: 2013-8-30 18:42
标题: 关于数组折半查找的练习不同的思路，不知可行性如何？
本帖最后由 路边小色狼 于 2013-8-31 14:54 编辑

练习：有一个有序数组，将一个元素插入到数组中且保证数组有序.如何获取该元素在数组中的位置？

    例子：int[] arr={2,4,5,7,19,32,45}; //要将元素8插入数组，要插入数组中的哪个位置？

   思路：if (arr[0]<8)     arr[0]=8; //如果数组第一个元素比8小，那把8赋值给第一个元素，
              然后把数组重新排序，再查找出8所在的位置，加1就是所要的位置;
             如果第一个元素比8还大，那8就放在第一位置。


这样感觉比折半查找的方法容易，可行吗？

作者: 范龙波    时间: 2013-8-30 19:00
本帖最后由 范龙波 于 2013-8-30 19:08 编辑

这么搞性能要比折半慢很多, 按照你的思路走 先对数组排序 , for的循环体要执行n的2次方 次  ,在找数组元素8的索引时, for的循环体又要执行 n次. 这么算你看看哪个性能好
作者: 月黑风高    时间: 2013-8-30 19:10
题目是：有一个有序数组，将一个元素插入到数组中且保证数组有序。
如何获取该元素在数组中的位置？

题目是有序数组，依次判断数组元素大小，第一个比元素大或者小（对应数组降序和升序）的下标就是元素插入位置，多方便啊，也不用重新排序！
作者: 路边小色狼    时间: 2013-8-30 19:15
月黑风高 发表于 2013-8-30 19:10
题目是：有一个有序数组，将一个元素插入到数组中且保证数组有序。
如何获取该元素在数组中的位置？

确实，你这样更简单
作者: 路边小色狼    时间: 2013-8-30 19:17
范龙波 发表于 2013-8-30 19:00
这么搞性能要比折半慢很多, 按照你的思路走 先对数组排序 , for的循环体要执行n的2次方 次  ,在找数组元素8 ...

有道理，没考虑到执行次数。
作者: 夏天那抹蓝╮    时间: 2013-8-31 11:06
楼主一定是误解了这个题目的意思了，
这其实就是传说中的插入法排序。
将一个元素插入进去，并保持有序。怎么才能做到呢？第一步是要找到“该插的位置”。然后第二步是插入。。等等的一些后续操作。
所以该问题问的是第一步如何实现，也就是找到该插的位置。（一定要注意找这个位置的目的是为了排序）

像楼主说的，排序后，再找它的位置，还有个毛用啊。
作者: 薛鹏鹏    时间: 2013-8-31 14:02

如果您的问题已经解决
请更改分类未解决为已解决
保持队形，谢谢合作

详情参考 如何修改分类




欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2