Leetcode 153 Find Minimum in Rotated Sorted Array

Soru

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:

[4,5,6,7,0,1,2] if it was rotated 4 times. [0,1,2,4,5,6,7] if it was rotated 7 times. Notice that rotating an array [a[0], a[1], a[2], …, a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], …, a[n-2]].

Given the sorted rotated array nums of unique elements, return the minimum element of this array.

You must write an algorithm that runs in O(log n) time.

Örnek 1

Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.

Örnek 2

Input: nums = [4,5,6,7,0,1,2]
Output: 0
Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.

Çözüm

• “153. Find Minimum in Rotated Sorted Array” sorusu, döndürülmüş bir sıralı dizide minimum değeri bulmanızı ister. Bu dizideki elemanlar önceden sıralanmışken, belirli bir pivot noktasında döndürülmüş; örneğin, [0,1,2,4,5,6,7] dizisi [4,5,6,7,0,1,2] şeklinde döndürülmüş olabilir. Soru, bu dizi içindeki en küçük elemanı bulmanızı istemektedir.
• Girdi: Döndürülmüş bir sıralı tam sayı dizisi nums.
• Çıktı: Dizideki minimum değer.
• Bu problem genellikle ikili arama (binary search) yöntemi kullanılarak çözülür. İkili arama yöntemi, döndürülmüş bir sıralı dizide minimum değeri bulmak için uygundur çünkü dizinin bir kısmı sıralı olacak şekilde döndürülmüştür. İkili arama kullanarak, her adımda dizinin bir yarısını diğerine göre daha az sıralı olup olmadığını kontrol ederek atlayabiliriz.
• Çalışma Mekanizması:
• Başlangıç ve Bitiş İşaretçileri: İkili arama için left ve right işaretçileri dizinin başlangıç ve bitişinde başlar.
• İkili Arama: left ve right işaretçileri birbirine eşit olana kadar ikili arama devam eder.
• Arama Koşulu: Her adımda, mid noktasının değeri ile right noktasının değeri karşılaştırılır: Eğer mid noktasının değeri, right noktasının değerinden büyükse, bu durum minimum değerin mid’in sağ tarafında olduğunu gösterir ve arama alanı mid + 1 ile right arasına daraltılır. Eğer mid noktasının değeri, right noktasının değerinden küçük veya eşitse, minimum değer mid noktasında veya onun sol tarafında olabilir; böylece arama alanı left ile mid arasına daraltılır.
• Sonuç: Döngü tamamlandığında, left işaretçisi minimum değere işaret eder.

Code

class Solution:
    def findMin(self, nums):
        left, right = 0, len(nums) - 1

        while left < right:
            mid = (left + right) // 2
            if nums[mid] > nums[right]:  # Minimum değer sağ tarafta olmalı
                left = mid + 1
            else:
                right = mid  # Minimum değer burada veya sol tarafta olabilir

        return nums[left]
      
    

Complexity

• Time complexity (Zaman Karmaşıklığı) : O(log n), burada n dizinin uzunluğudur. İkili arama her adımda arama alanını yarıya indirger.
• Space complexity (Alan Karmaşıklığı) : O(1), çünkü ekstra alan kullanılmaz.