數(shù)據(jù)結(jié)構(gòu)與算法（查找和排序） --javascript語言描述

Stardustsky 發(fā)布于2019-08-26 11:45 / 622人閱讀

摘要：如此，便可以縮小搜索范圍，提高時間復(fù)雜度，最終第一個指針指向前面子數(shù)組的最后一個元素，而第二個指針指向后面子數(shù)組的第一個元素，它們處于相鄰位置，而第二個指針指向的剛好是最小的元素。

旋轉(zhuǎn)數(shù)組的最小數(shù)字（二分查找）

把一個數(shù)組最開始的若干個元素搬到數(shù)組的末尾，我們稱之為數(shù)組的旋轉(zhuǎn)。輸入一個非遞減排序的數(shù)組的一個旋轉(zhuǎn)，輸出旋轉(zhuǎn)數(shù)組的最小元素。例如數(shù)組{3,4,5,1,2}為{1,2,3,4,5}的一個旋轉(zhuǎn)，該數(shù)組的最小值為1。 NOTE：給出的所有元素都大于0，若數(shù)組大小為0，請返回0。

思路：

1.設(shè)置兩個指針，初始狀態(tài)第一個指針指向前面子數(shù)組的第一個元素，第二個指針指向后面子數(shù)組的最后一個元素；

2.找到兩個指針的中間元素；

3.若其大于等于第一個指針指向的元素，則說明其在前面的子數(shù)組中，且顯然最小元素在中間元素的右邊，若其小于等于第二個指針指向的元素，則說明其在后面的子數(shù)組中，且顯然最小元素在中間元素的左邊。

如此，便可以縮小搜索范圍，提高時間復(fù)雜度，最終第一個指針指向前面子數(shù)組的最后一個元素，而第二個指針指向后面子數(shù)組的第一個元素，它們處于相鄰位置，而第二個指針指向的剛好是最小的元素。

注意：按旋轉(zhuǎn)規(guī)則，第一個元素應(yīng)該是大于或等于最后一個元素的；但也有特例：若把排序數(shù)組的前0個元素搬到最后面，及排序數(shù)組本身，仍是數(shù)組的一個旋轉(zhuǎn)，此時數(shù)組中的第一個數(shù)字是最小的數(shù)字。

注意：當兩個指針指向的數(shù)字及它們中間的數(shù)字三者相等時，無法判斷中間數(shù)字位于前面的子數(shù)組還是后面的子數(shù)組，也就無法移動兩個指針來縮小查找的范圍，此時只能用順序查找的方法。

例如：數(shù)組{1,0,1,1,1}和數(shù)組{1,1,1,0,1}都可看成是遞增數(shù)組{0,1,1,1,1}的旋轉(zhuǎn)。第一種情況，中間數(shù)字位于后面的子數(shù)組，第二種情況，中間數(shù)字位于前面的子數(shù)組。

function minNumberInRotateArray(arr) {
  let index1 = 0;
  let index2 = arr.length - 1;
  let indexMid = index1;
  while(arr[index1] >= arr[index2]) {
    if(index2 - index1 == 1) {
      indexMid = index2;
      break;
    }
    indexMid = Math.floor((index1 + index2 ) / 2);
    //如果下標為index1、index2和indexMid指向的三個數(shù)字相等
    //則只能順序查找
    if(arr[index1] == arr[index2] && arr[indexMid] == arr[index1]) {
      return MininOrder(arr,index1,index2);
    }
    if(arr[indexMid] >= arr[index1]) {
      index1 = indexMid;
    }
    if(arr[indexMid] <= arr[index2]) {
      index2 = indexMid;
    }
  }
  return arr[indexMid];
}

//按順序查找函數(shù)
function MininOrder(arr,index1,index2) {
  let res = arr[index1];
  for (var i = index1 + 1; i <= index2; i++) {
    if(res > arr[i]) {
      res = arr[i];
    }
  }
  return res;
}

console.log(minNumberInRotateArray([3,4,5,1,2]));