搜索旋转排序数列

addendum777

int search(int* nums, int numsSize, int target){
    int i,j;
    int lens=0;
    int * result=(int *)malloc(sizeof(int)*numsSize);
    for(i=0;nums[i]!='\0';i++)
    {
        lens++;
    }

    if(target>lens)
    return -1;//不存在这个目标值

    for(i=target,j=0;i<numsSize-1;i++,j++)
    {
        result[j]=nums[i];
    }
    for(i=0,j=(numsSize-target);i<target;i++)
    {
        result[j]=nums;
    }
    return result[target];


}哪里出现了问题[/i][/i]

jhq999

看来语文不好，才看明白什么意思，就是把本来有序的数组在某处被旋转了，让你以最小的复杂度来判断在否存在，存在给出下标

jhq999

#include<stdio.h>

int search(int num[],int n,int target)
{
    int i=0,j=n-1,k=0;
    while(num[i]>num[j])
    {
        k=(i+j)/2;
        if(num[k]>num[i])i=k;
        else j=k;

    }////先折半查找出最大,也就是分界线

    if(target>=num[0])i=0,j=k;
    else if(target<=num[n-1])i=k+1,j=n-1;////判断target在那个段里

    while(i<j-1)//////////再在这个段里折半查找
    {
        k=(i+j)/2;
        if(target>num[k])i=k;
        else j=k;

    }
    if(target==num[i])return i;
    else if(target==num[j])return j;
    return -1;
}
int main()
{
    int num[]={3,4,5,6,7,9,16,0,1};
    printf("%d",search(num,9,16));
    return 0;
}

傻眼貓咪

#include <stdio.h>

int foo(int nums[], int size, int target) {
        if (target < nums[0]) {
                for (int i = size - 1; ; --i) {
                        if (nums[i] == target) {
                                return i;
                        }
                        if (nums[i] < nums[i - 1]) {
                                break;
                        }
                }
        }
        else {
                for (int i = 0; ; ++i) {
                        if (nums[i] == target) {
                                return i;
                        }
                        if (nums[i] > nums[i + 1]) {
                                break;
                        }
                }
        }
        return -1;
}

int main(void) {
        int nums[] = { 4, 5, 6, 7, 0, 1, 2};
        printf("%d", foo(nums, 7, 0));

        return 0;
}

ExiaGN001

这道题全部时间复杂度下限是o(n)

两种做法：
1、
o(n)读数据
o(n* log2 n)快排 或 o(n)基数排序
o(log2 n)二分查找

2.
o(n)读数据
o(n)直接查找