搜索旋转排序数组

题目描述
给出一个转动过的有序数组，你事先不知道该数组转动了多少
(例如,0 1 2 4 5 6 7可能变为4 5 6 7 0 1 2).
在数组中搜索给出的目标值，如果能在数组中找到，返回它的索引，否则返回-1。
假设数组中不存在重复项。

解法

    //解法：二分查找
    // 先根据 nums[mid] 与 nums[lo] 的关系判断 mid 是在左段还是右段
    // 接下来再判断 target 是在 mid 的左边还是右边，从而来调整左右边界 lo 和 hi
    //时间：O（logN） 空间O（1）
    int search(int* A, int n, int target) {
        int lo = 0, hi = n - 1;
        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            if (A[mid] == target) return mid;
            if (A[mid] >= A[0]) { // mid 是在左段
                if (target < A[mid] && target >= A[lo]) {
                    hi = mid - 1;
                } else {
                    lo = mid + 1;
                }
            } else { //mid 在右段
                if (target > A[mid] && target <= A[hi]) {
                    lo = mid + 1;
                } else {
                    hi = mid - 1;
                }
            }
        }
        return -1;
    }