[LeetCode]Search in Rotated Sorted Array

题目：Search in Rotated Sorted Array

给定一个升序但绕某一个值旋转的数组，找到给定的目标值的下标，没找到返回-1.

思路：

第一个值和最后一个值是旋转后被分成的两个升序数组的临界值，第一个值是较大的数组的最小值，最后一个值是较小的数组的最大值。

判断target在哪个数组后用二分查找找到目标值的位置即可。

注意：

当最后一个值<target<第一个值时，则找不到target。

/***************************************************************************************************
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.
***************************************************************************************************/
#include<stdio.h>

int search(int* nums, int numsSize, int target) {
    int leftMin = nums[0];
    int rightMax = nums[numsSize - 1];
    if(target < leftMin && target > rightMax)return -1;//target不再数组中
    if(target == leftMin)return 0;
    if(target == rightMax)return numsSize - 1;

    int center = numsSize/2;
    int left = 0,right = numsSize - 1;
    if(target > leftMin){//在较大的数组中
        while(left <= right){
            if(nums[center] == target)return center;
            if(nums[center] < target){
                if(nums[center] >= leftMin){
                    left = center + 1;
                    if(nums[left] < leftMin)return -1;
                    center = (left + right)/2;
                }else{
                    right = center - 1;
                    center = (left + right)/2;
                }
            }else{
                  right = center - 1;
                  center = (left + right)/2;
            }
        }
      }else{//在较小的数组中
          while(left <= right){
            if(nums[center] == target)return center;
            if(nums[center] < rightMax){
                if(nums[center] > target){
                    right = center - 1;
                    if(nums[right] > rightMax)return -1;
                    center = (left + right)/2;
                }else{
                    left = center + 1;
                    center = (left + right)/2;
                }
            }else{
                left = center + 1;
                  center = (left + right)/2;
            }
        }
      }

      return -1;
}

void main(){
    int a[] = {4,5,6,7,0,1,2};

    printf("%d
",search(a,sizeof(a)/sizeof(int),1));
}

还有一道更复杂一点题目

题目：Search for a Range

升序排列的数组，有重复元素，在O(logN)的复杂度下找到给定元素的所在范围。没有是[-1,-1]。

思路：

先通过二分查找找到目标值的位置，在两边扩充找到其范围。

/***************************************************************************************************
Given an array of integers sorted in ascending order, find the starting and ending position of a given target value.
Your algorithm's runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].
For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].
***************************************************************************************************/
#include<stdio.h>

/**
 * Return an array of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* searchRange(int* nums, int numsSize, int target, int* returnSize) {
        int *retArray = (int *)malloc(2*sizeof(int));
        retArray[0] = -1;
        retArray[1] = -1;
        *returnSize = 2;
        if(target > nums[numsSize - 1])return retArray;

    int flag = 0,left = 0,right = numsSize - 1;
    int center = (left + right)/2;
    while(left <= right){//二分查找
        if(nums[center] == target){
            flag = 1;
            break;
        }else if(nums[center] > target){
            right = center - 1;
            while(right >= left && nums[right] == nums[right + 1])right--;//跳过重复值
            center = (left + right)/2;
        }else{
            left = center + 1;
            while(right >= left && nums[left] == nums[left - 1])left++;//跳过重复值
            center = (left + right)/2;
        }
    }

    if(flag == 1){//找到目标值，就两边扩充所有的目标值
        left = center - 1;
        right = center + 1;
        while(left >= 0 && nums[left] == nums[center])left--;
        while(right < numsSize && nums[right] == nums[center])right++;
            retArray[0] = left + 1;
            retArray[1] = right - 1;
    }

    return retArray;
}

void main(){
    int size = 0;
    int a[] = {5,7,7,8,8,10};
    int *num = searchRange(a,sizeof(a)/sizeof(int),10,&size);

    for(int i = 0;i < size;i++){
        printf("%d ",num[i]);
    }

    free(num);
}