一个有关查找的算法 问题

ganqing1234

问题：一个有序数组a[0,n-1]，查找x是否在其中。
1. x 不在数组中则返回比 x 小的最大元素的下标 i 和比 x 大的最小元素的下标 j ;
2. x 在数组中则 i=j ,它们都指向数组中与 x 相等的元素的下标。

希望各位踊跃参加，写出思路即可，完整代码则更好。谢谢!

mingyanguo

O(log n)吧
相当于每个元素都减去x，然后找最小正数与最大负数，或者0的下标。



[ 本帖最后由 mingyanguo 于 2006-3-18 18:59 编辑 ]

converse

二分查找不是更快一些么？

mingyanguo

原帖由 converse 于 2006-3-17 21:30 发表
二分查找不是更快一些么？

没看见那个“有序”的条件。。。。。。。。
我改~~~~~~

ganqing1234

二分查找是更好,这里只是练练其他的算法.
老实说,这是 计算机算法设计 的课外作业,我想了一下,不会做,才希望大家一起想想的
感谢二位回复!

pcboyxhy

二分法 或者3分法
最佳的应该是 2.57....分
呵呵

lenovo

原帖由 mingyanguo 于 2006-3-17 22:59 发表


没看见那个“有序”的条件。。。。。。。。
我改~~~~~~

二楼就是你改的答案？

小灰狼@广州

站在数组前叫一声 `x'，`x' 听到后自己跳出来。这个是  O(1) 的，叫并行搜索。:em11:

mingyanguo

原帖由 lenovo 于 2006-3-18 18:01 发表

二楼就是你改的答案？

偶不会了谁会写一下啊~~

lenovo

原帖由 mingyanguo 于 2006-3-18 18:08 发表


偶不会了谁会写一下啊~~

二分查找的话，
应该是O(logn)吧？