/**
 * NOTE: 在一個(gè)循環(huán)有序的列表中查找指定的值。
 * 比如[6,7,8,1,2,3,4,5]就是一個(gè)循環(huán)有序數(shù)組。
 * 時(shí)間復(fù)雜度: O(logn), 空間: O(1)
 * 移動(dòng)中軸; 找到有序的序列, 然后從有序的序列中找到 target
 */

function find(list, target) {
  if (list.length === 0) {
    return -1
  }
  let start = 0
  let end = list.length - 1
  const res = []
  while (start <= end) {
    const mid = start + ((end - start) >> 1)
    if (list[mid] === target) {
      res.push(mid)
    }

    if (list[mid] >= list[start]) {
      // target 在 start - mid 之間
      if (target >= list[start] && target <= list[mid]) {
        end = mid - 1
      } else {
        // target 不在 start - mid 之間
        start = mid + 1
      }
    } else {
      if (target >= list[mid] && target <= list[end]) {
        start = mid + 1
      } else {
        end = mid - 1
      }
    }
  }
  return res
}

// test
const a = find([7, 7, 8, 9, 1, 2, 5, 6, 7, 9], 5);
console.log(a)
/*
  0: mid 4 = 1 , start: 0, 7; end 9, 9 =>
  1: mid 7, end: 9 start 5;
 */
// // const b = find([7, 7, 8, 9, 1, 2, 5, 6, 7, 7], 4);
// // const c = find([7, 7, 8, 9, 1, 2, 5, 6, 7, 7], 7);

// console.log(a, b, c);