在数组a中查找某个数,若找到,则输出该数在下面程序的功能是在a数组中查找的位置,否则输出"查无此数!"。麻烦帮填下横线位置

数组A中任意两个相邻元素大小相差1现给定这样的数组A和目标整数t,找出t在数组A中的位置

很明显,在下面程序的功能是在a数组中查找寻找某个数的复杂度为O(n)但在某些特殊下面程序的功能是在a数组中查找,可以通过寻找规律来减少比较次数

上述数组的规律就是:相邻元素相差1,奇偶交替排列

如果某個数A[i]等于要查找的数x,那么由于奇偶交替排列的关系可以跳过下个数A[i+1],即i=i+2;

如果某个数A[i]不等于要查找的数x那么由于相邻元素相差1,可鉯跳过x-A[i]的绝对值个数即i=i+abs(x-A[i])

通过数组的规律来进行查找,可以减少一半以上的时间复杂度

}

题目源自于leetcode二分查找题。

思路:有序数组所以查找目标的数一定是连续的在某个范围上。我们是要通过二分查找找到这些相同的数的最左端的一个、和最右端的一个不管是左端还是右端,指定合理的二分策略一定都是可以找到的。

寻找目标数最左端的二分策略:

mid = (high+low)/2;//如果分段内有奇数个数mid位于正中間;如果有偶数个数,mid位于左中间

寻找目标数最右端的二分策略:

else //找到目标数时优先向右二分
}

我要回帖

更多关于 下面程序的功能是在a数组中查找 的文章

更多推荐

版权声明:文章内容来源于网络,版权归原作者所有,如有侵权请点击这里与我们联系,我们将及时删除。

点击添加站长微信