Tìm phần tử nhỏ nhất trong một mảng đã sắp xếp được xoay vòng trong JavaScript

Chúng tôi được yêu cầu viết một hàm JavaScript lấy một mảng số nguyên làm đối số duy nhất.

Đầu tiên, mảng được sắp xếp và sau đó được xoay vòng theo bất kỳ số phần tử tùy ý nào. Các hàm của chúng ta nên tìm phần tử nhỏ nhất trong mảng và trả về phần tử đó.

Điều kiện duy nhất là chúng tôi phải làm điều này với độ phức tạp thời gian tuyến tính thấp hơn, có thể sử dụng phiên bản đã được chỉnh sửa đôi chút của thuật toán tìm kiếm nhị phân.

Ví dụ -

Nếu mảng đầu vào là -

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

Sau đó, đầu ra phải là 2.

Ví dụ

Sau đây là mã -

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));

Đầu ra

Sau đây là đầu ra của bảng điều khiển -

2