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

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

题目

这张图好像是击败百分百的内存消耗,其他99、98的都有个竖线显示。

升序排列的整数数组 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;
}

You may also like...

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注