การหาค่าน้อยที่สุดในอาร์เรย์ที่ถูก rotate จาก sorted array ใน JavaScript

บทความนี้สาธิตการหาค่าน้อยที่สุดใน rotated sorted array ใช้ binary search แบบปรับเปลี่ยน O(log n)

ตัวอย่าง

arr = [6, 8, 12, 25, 2, 4, 5] -> min = 2

ตัวอย่างโค้ด

const arr = [6, 8, 12, 25, 2, 4, 5];

const findMin = (arr = []) => {
  let temp;
  let min = 0;
  let max = arr.length - 1;
  let currentMin = Number.POSITIVE_INFINITY;
  while (min <= max) {
    temp = (min + max) >> 1;
    currentMin = Math.min(currentMin, arr[temp]);
    if (arr[min] < arr[temp] && arr[temp] <= arr[max] || arr[min] > arr[temp]) {
      max = temp - 1;
    } else if (arr[temp] === arr[min] && arr[min] === arr[max]) {
      let guessNum = arr[temp];
      while (min <= max && arr[min] === guessNum) {
        min++;
      }
    } else {
      min = temp + 1;
    }
  }
  return currentMin;
};

console.log(findMin(arr));

ผลลัพธ์

2

คำอธิบาย

Binary search หาจุดที่ array "wrap around" (จุดที่ค่าลดลง)

เงื่อนไข: หาก left < mid <= right -> sorted ปกติ min อยู่ซ้าย mid

หาก left > mid -> rotation point อยู่ซ้าย mid

จัดการ duplicate ด้วยการขยับ left