NowCoder：元素查找（二分法）

入口戳这里

有一个排过序的数组，包含n个整数，但是这个数组向左进行了一定长度的移位，例如，原数组为[1,2,3,4,5,6]，向左移位5个位置即变成了[6,1,2,3,4,5],现在对于移位后的数组，需要查找某个元素的位置。请设计一个复杂度为log级别的算法完成这个任务。

给定一个int数组A，为移位后的数组，同时给定数组大小n和需要查找的元素的值x，请返回x的位置(位置从零开始)。保证数组中元素互异。

测试样例：

[6,1,2,3,4,5],6,6

返回：0

分析：
题目的解题思路就是二分查找，但是具体的细节有待研究，虽说是二分查找，但是想要把细节搞清楚也要点时间，这里就分析一下流程

一次 “二分” 后 mid 可能落在的位置大致就分为两段，第一段 begin 开始到断点结束，第二段是断点开始到 end 结束

首先如果 mid 落在了断点之前，x 的可能位置就变为了三段，第一段 begin-mid、第二段 mid-断点、第三段 断点-end

if (x在第一段)
	end = mid - 1;
else if (x在第二段 || x在第三段)
	begin = mid + 1;

如果 mid 落在了断点之后，同样 x 的位置也是三段，第一段 begin-断点、第二段 断点-mid、第三段 mid-end

if (x在第一段 || x在第二段)
	end = mid - 1;
else if (x在第三段)
	begin = mid + 1;

代码实现

class Finder {
public:
    int findElement(vector<int> A, int n, int x) {
        int begin = 0;
        int end = n-1;
        while (begin <= end) {
            int mid = (begin + end) >> 1;
            if (A[mid] == x) {
                return mid;
            }
            // mid 在断点之前
            else if (A[mid] > A[begin]) {
                if (x < A[mid] && x >= A[begin]) end = mid - 1;
                else begin = mid + 1;
            } 
			// mid 在断点之后
			else {
                if (x > A[mid] && x <= A[end]) begin = mid + 1;
                else end = mid - 1;
            }
        }
        return -1;
    }
};