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

Chúng ta cần viết một hàm JavaScript nhận vào một mảng số nguyên làm đối số duy nhất.

Mảng được sắp xếp trước rồi xoay bởi một số tùy ý các phần tử. 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 ta phải làm trong độ phức tạp thời gian nhỏ hơn tuyến tính, có thể dùng phiên bản điều chỉnh 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];

Thì đầu ra nên là 2.

Ví dụ

Dưới đây là mã nguồn:

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

Kết quả

Đầu ra trên console:

2

Giải thích: Tìm min trong rotated sorted array (LeetCode 153). Binary search so sánh mid với left/right để quyết định đi bên nào. Code xử lý cả trường hợp duplicates (arr[min]==arr[mid]==arr[max] → shrink left). O(log n) average, O(n) worst với nhiều duplicates.