LeetCode 解答 #33. Search in Rotated Sorted Array プログラミング練習

問題：

難易度:　medium
入力:　int型array、(int)target
目的: 入力されたarrayの中で、targetの値と一致するエレメントのindexを求めよ
出力:　int

入力のArrayはソートされているが、どこかでRotateされている。
例えば[1,2,3,4,5]がどこかでくねり、[3,4,5,1,2]になって入力されるのだ。
その入力の中でtargetと一致する数字を探せばいいのだ。

注意すべき事:　

• 一致する数字がない場合は-1を返す。

• 時間複雑度はO(logn)に抑えるべき。

• 重複するエレメントは存在しない。

以下回答です。
O(logn)に抑えろとの事なのでバイナリサーチを使うべき。
しかしどこかでRotateしているのなら左右から探した方が場合によっては速いのでは？
と思ったので二つの方法で書いてみました。

まずはバイナリサーチ:

class Solution {
    public int search(int[] nums, int target) {
        if (nums.length == 0) return -1;
        int start = 0, end = nums.length - 1;
        return binarysearch(nums, target, start, end);
    }
    
    public int binarysearch(int[] nums, int target, int start, int end) {
        if (start > end) return -1;
        int mid = (start + end) / 2;
        if (nums[mid] == target) return mid;
        if (nums[start] <= nums[mid]) {
            if (nums[start] <= target && nums[mid] >= target) {
                return binarysearch(nums, target, start, mid-1);
            } else {
                return binarysearch(nums, target, mid+1, end);
            }
        } 
        if (nums[mid] <= nums[end]) {
            if (nums[mid] <= target && nums[end] >= target) {
                return binarysearch(nums, target, mid+1, end);
            } else {
                return binarysearch(nums, target, start, mid-1);
            }
        }
        return -1;
    }
}

続けて普通のサーチ:

class Solution {
    public int search2(int[] nums, int target) {
        if (nums.length == 0) return -1;
        int first = nums[0];
        int sec = nums[nums.length - 1];
        if (Math.abs(first-target) < Math.abs(sec - target)) {
            for (int i=0; i<nums.length; i++) {
                if (nums[i] == target) return i;
            }
        }
        else {
            for(int i=nums.length-1; i>=0; i--) {
                if (nums[i] == target) return i;
            }
        }
        return -1;
    }
}

バイナリサーチのワーストケースはO(logn)で二番目の方法のワーストケースはO(n)です。
しかし結果二番目の方法の方が若干速かったです。
もちろん面接にこの問題が出た場合はバイナリサーチの方が良い答えなのですが、
あまり偏ったテストケースじゃない限りあまり変わらないようですね。
問題としてはRotateされているとは言えソートされたArrayなのでどちらも標準アルゴリズムを少し変えた程度です。

今日は以上。
よいプログラミング生活を！