JavaScript में घूमी हुई क्रमबद्ध सरणी में सबसे छोटा तत्व ढूंढना

हमें एक JavaScript फ़ंक्शन लिखना है जो एकमात्र तर्क के रूप में पूर्णांकों की एक सरणी लेता है।

सरणी पहले क्रमबद्ध होती है और फिर तत्वों की मनमानी संख्या से घुमाई (rotated) जाती है। हमारे फ़ंक्शन को सरणी में सबसे छोटा तत्व ढूंढना चाहिए और वह तत्व वापस करना चाहिए।

एकमात्र शर्त यह है कि हमें इसे रैखिक समय जटिलता से कम में करना है, शायद बाइनरी खोज एल्गोरिदम के कुछ संशोधित संस्करण का उपयोग करके।

उदाहरण के लिए -

यदि इनपुट सरणी है -

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