0033-搜索旋转排序数组

搜索旋转排序数组

方案一

如果中间的数小于最右边的数，则右半段是有序的，若中间数大于最右边数，则左半段是有序的，我们只要在有序的半段里用首尾两个数组来判断目标值是否在这一区域内，这样就可以确定保留哪半边了。

C-源代码

int search1(int* nums, int numsSize, int target) {
    int left = 0;
    int right = numsSize - 1;
    while (left <= right) {
        int mid = left + ((right - left) >> 1);
        if (nums[mid] == target) {
            return mid;
        }
        else if (nums[mid] < nums[right]) {
            if (nums[mid] < target && nums[right] >= target) {
                left = mid + 1;
            }
            else {
                right = mid - 1;
            }
        }
        else {
            if (nums[left] <= target && nums[mid] > target) {
                right = mid - 1;
            }
            else {
                left = mid + 1;
            }
        }
    }
    return -1;
}

void test_0033(void) {
    int arr[7] = { 4,5,6,7,0,1,2 };
    int len = sizeof(arr) / sizeof(arr[0]);
    int target = 0;
    int ret = search1(arr, len, target);
    printf("ret = %d\n", ret);
    
    int target1 = 3;
    int ret1 = search1(arr, len, target1);
    printf("ret = %d\n", ret1);
}

参考Grandyang