ค้นหาองค์ประกอบที่เล็กที่สุดในอาร์เรย์ที่เรียงลำดับซึ่งหมุนใน JavaScript

เราจำเป็นต้องเขียนฟังก์ชัน JavaScript ที่รับอาร์เรย์ของจำนวนเต็มเป็นอาร์กิวเมนต์เท่านั้น

อาร์เรย์จะถูกจัดเรียงก่อนแล้วจึงหมุนตามจำนวนองค์ประกอบตามอำเภอใจ ฟังก์ชันของเราจะค้นหาองค์ประกอบที่เล็กที่สุดในอาร์เรย์และส่งคืนองค์ประกอบนั้น

เงื่อนไขเดียวคือ เราต้องทำสิ่งนี้โดยใช้เวลาน้อยกว่าความซับซ้อนของเวลาเชิงเส้น อาจใช้อัลกอริธึมการค้นหาแบบไบนารีในเวอร์ชันที่ปรับแต่งแล้ว

ตัวอย่างเช่น −

หากอาร์เรย์อินพุตเป็น −

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

จากนั้นผลลัพธ์ควรเป็น 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