錯位陣列內搜尋指定數字

這題可參考:

一如往常,寫個二分遞迴:

search(nums, target) = search(nums, target, i, n/2) || search(nums, target, i + n/2, n - n/2);

切到未錯位子陣列後,就可快速判斷此範圍內是否包含 target ,否之直接回傳。

類似二元搜尋,所以平均複雜度會是 O(logn) 最差 O(n)。

是否錯位判斷很簡單,最左永小於最右:

nums[i] < nums[j]

在沒有錯位的排序陣列中,可快速判斷此範圍內是否包含 target:

if (nums[i] < nums[j]) {
if (target < nums[i]) return false;
if (nums[j] < target) return false;
}

還有錯位繼續切,直到沒得切就直接判斷 target 。

延伸題:回傳指定數值的位置

雖然是題目顯示這是前一題,剛好筆者先做第二題且發現第一題程式碼反比較難以閱讀,此題視為延伸題: