problem

輸入為一個陣列和一個整數 target。陣列有排序，元素為不重複的整數，但是所有的元素往左或往右 '移位' 了一個或多個位置，例如陣列 [1, 2, 3, 4] 可能變成 [3, 4, 1, 2]。以二元搜尋為想法檢查 target 是否在陣列中，有則回傳索引值，否則回傳 -1。

sample input:
array = [45, 59, 64, 72, 73, 0, 5, 21, 32, 37],
target = 32

sample output:
8

這題延續昨天的二元搜尋。原本的二元搜尋利用左右兩個指標算出中間索引後，比較中央數字和目標數字，來將陣列的左半邊或右半邊排除，但這個方法用在移位後的陣列上可能會出錯，所以步驟稍作修改：

1. 一樣比較中央數字和目標數字，如果相同，回傳索引。
2. 接下來比較左邊數字和中央數字，如果左 <= 中，代表左半邊有排序，所以檢查目標是否在左邊，是則在左邊繼續搜尋。
3. 承上，如果左 > 中，代表左半邊無序，右半邊必為有序，所以檢查目標是否在右邊，是則在右邊繼續搜尋。

也就是相較於原本的作法，在比較中央數字和目標數字後，再增加了幾次比較，
→ 先確定哪一邊的陣列是有序的
→ 就可以確認目標是否在有序的一邊
→ 就可以確認要排除哪一邊

寫成虛擬碼的話，大致可以表達成如下 (此處暫時不區分指標以及其指向的數字)：

if mid == target:
  return mid

// 左半邊有序
if left <= mid:
  if target < mid AND target >= left:
    explore left half
  else
    explore right half
// 右半邊有序
else 
  if target > mid AND target <= right:
    explore right half
  else
    explore left half

跟原本的二元搜尋一樣，n 為輸入陣列長度，
time: O(log(n))
space: O(1)

以下程式碼是疊代的寫法，另外一樣可以寫成遞迴的方式，只是遞迴寫法的空間複雜度會因為堆疊變為 O(log(n))。

function shiftedBinarySearch(array, target) {
  let left = 0, right = array.length - 1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    const midNum = array[mid], leftNum = array[left], rightNum = array[right];
    if (midNum === target) return mid;
    if (leftNum <= midNum) {
      if (target < midNum && target >= leftNum) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    } else {
      if (target > midNum && target <= rightNum) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
  }
  return -1;
}