Question

这道关于《数据结构》的题该如何做呢？

Answer 1

如果与后继元素位置交换了岂不是就不再递增有序了？...那么就没有什么性质了？

不过看题目意思好像是只要求进行一次操作，而且只要求查找到它的时间最短。

有一种比较简单的做法，就是二分法。
每次二分这个有序数组中的一个位置mid=(l+r)/2。然后判断这个元素和x的大小关系。
如果a[mid]>x，那么可以将r移动到mid，如果a[mid]>=x，那么可以将l移动到mid。一直到区间大小为1，就是那个元素。
其中l的初始值为1.r的初始值为n。

上面只是查找方法，但是数组中的添加很慢。
所以可以使用一种神奇的数据结构叫平衡树或者二叉搜索树。[但是一看就不是要问这个]。