LeetCode-中等-33-搜索旋转排序数组-二分法(C)

这个内存刷到5.7MB的时候有几率出现击败百分百，但是没和0ms一起刷出来...

题目

升序排列的整数数组 nums 在预先未知的某个点上进行了旋转（例如， [0,1,2,4,5,6,7] 经旋转后可能变为 [4,5,6,7,0,1,2] ）。

请你在数组中搜索 target ，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。

示例 1：

输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4
示例 2：

输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1
示例 3：

输入：nums = [1], target = 0
输出：-1
 

提示：

1 <= nums.length <= 5000
-10^4 <= nums[i] <= 10^4
nums 中的每个值都 独一无二
nums 肯定会在某个点上旋转
-10^4 <= target <= 10^4

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/search-in-rotated-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

• 用二分法的思想来解决这题。
• 举四个例子来判断所有的情况：
  • 1245670
  • 2456701
  • 4567012
  • 6701245
• 因为这原本就是个升序数列，所以最后一个与第一个值必然是相邻的，可以简化代码量。
• 然后通过这些例子可以得知：
  • 如果目标值比中间、两边都小，或者都大：
    • 如果中间比两边大，往右边寻找。
    • 如果中间比两边小，往左边寻找。
  • 如果目标值比中间小，比两边大：
    • 往左边寻找。
  • 如果目标值比中间大，比两边小：
    • 往右边寻找。
• 再用递归实现这个二分法即可。

代码

/*
如果目标值比中间、两边都小，或者都大：
    如果中间比两边大，往右边寻找。
    如果中间比两边小，往左边寻找。
如果目标值比中间小，比两边大：
    往左边寻找。
如果目标值比中间大，比两边小：
    往右边寻找。
如果两边相同，返回-1。
如果找到该值，返回索引。
*/
int searchTwoDivide(int* nums, int left, int right, int target);

int search(int* nums, int numsSize, int target){
    return searchTwoDivide(nums, 0, numsSize-1, target);
}

int searchTwoDivide(int* nums, int left, int right, int target){
    int midPos = (left+right) / 2;
    if(target == nums[left]) return left;
    else if(target == nums[right]) return right;
    else if(target == nums[midPos]) return midPos;
    else if(left == right || midPos == left) return -1;
    else if( (target < nums[midPos] && target < nums[right]) || (target > nums[midPos] && target>nums[right])){
        if(nums[midPos] > nums[right]) return searchTwoDivide(nums, midPos, right, target);
        else return searchTwoDivide(nums, left, midPos, target);
    }
    else if(target < nums[midPos] && target > nums[right]) return searchTwoDivide(nums, left, midPos, target);
    else if(target > nums[midPos] && target < nums[right]) return searchTwoDivide(nums, midPos, right, target);
    return -1;
}