どこへ行って試験問題を書きます——配列を並べて循環してシフトした後に探します

配列を並べ替えて循環シフトした後に検索

タイトル:

次のアルゴリズムを完了して、循環秩序のある配列を指定して、この配列の中で指定した要素を見つけて、見つけたら下付きを返して、返し-1が見つかりません。このデータの特徴は,単調に増加した配列が右に循環シフトして形成されることである。例として、元の配列は[4,8,13,20,23,34,41,52]が右方向に循環シフトした後に形成される配列は、[23,34,41,52,4,8,13,20]であってもよいし、[4,8,13,20,23,34,41,52]第1行入力配列の長さの第2行は配列の要素であり、第3行をスペースで区切って検索したい要素サンプル入力7 1 3 5 6 8,10,19サンプル出力-1である

考え方:
1>並べ替え(時間の複雑さはn*lognが最も低く、考慮しない)
2>直接シーケンス検索(時間複雑度n)
3>最適化された順序検索、1回のスキャン、両方のヘッドを比較(時間複雑度n)
コード:

int my_lookup(int *list,int len, int target){
    int i = 0;
    for( i  = 0 ; i <= (len/2 + 1) ; i++){
        if(list[i] == target){
            return i;
        }
        else if(list[len - i - 1] == target){
            return len - i - 1;
        }
    }
    return -1;
}

以上のコードがコミットされ、ACされています.
4>二分検索で、配列を2つの増分配列に分割し、二分検索を使用します.(時間複雑度logn)
コード:

int my_lookup(int *list, int len, int target){
    int left = 0;
    int right = len - 1;
    int mid = (left + right) / 2;
	while(left <= right){
	    if(list[mid] == target) return mid;
        if(list[left] == target) return left;
        if(list[right] == target) return right;
        if(list[left] <= list[mid]){
            if(list[left] < target && target < list[mid]){
                left++;
                right = mid - 1;
            }else{
                left = mid + 1;
                right--;
            }
        }else{
            if(list[mid] < target && target < list[right]){
                left = mid + 1;
                right--;
            }else{
                left++;
                right = mid - 1;
            }
        }
        mid = (left + right) / 2;
	}
	return -1;
}