Leetcode 33 Search in Rotated Sorted Array

Soru

There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

You must write an algorithm with O(log n) runtime complexity.

Örnek 1

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Örnek 2

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

Çözüm

• “33. Search in Rotated Sorted Array” sorusu, önceden sıralanmış bir dizinin döndürüldüğü bir versiyonunda belirli bir hedef değeri aramanızı ister. Dizi, önce sıralanmış ve ardından belirli bir pivot noktasında döndürülmüştür, yani dizi kısmen sıralıdır.
• Girdi: Döndürülmüş bir sıralı tam sayı dizisi nums ve bir hedef sayı target.
• Çıktı: Eğer target dizide varsa, onun indeksini döndürün. Yoksa -1 döndürün.
• Bu problem, ikili arama (binary search) kullanılarak çözülebilir. Ancak, dizinin döndürülmüş olması, doğrudan ikili aramanın uygulanmasını karmaşıklaştırır. Bunun yerine, ikili arama sırasında dizinin hangi kısmının sıralı olduğunu belirleyip, target değerinin o kısımda olup olmadığını kontrol etmek gerekir.
• Çalışma Mekanizması:
• Başlangıç ve Bitiş İşaretçileri: left ve right işaretçileri dizinin başlangıç ve bitişinde başlar.
• İkili Arama: Döngü, left işaretçisi right işaretçisinden küçük veya eşit olduğu sürece devam eder.
• Pivot Kontrolü ve İkili Arama Uygulaması: Eğer sol taraf sıralıysa (nums[left] <= nums[mid]), target’ın bu aralıkta olup olmadığını kontrol edilir. Eğer aralıktaysa, arama bu yarıda devam eder. Eğer sağ taraf sıralıysa (nums[mid] <= nums[right]), target’ın bu aralıkta olup olmadığını kontrol edilir. Eğer aralıktaysa, arama bu yarıda devam eder.
• Sonuç: target bulunursa indeksi, bulunamazsa -1 döndürülür.

Code

class Solution:
    def search(self, nums, target):
        left, right = 0, len(nums) - 1
        
        while left <= right:
            mid = (left + right) // 2
            
            if nums[mid] == target:
                return mid
            
            # Sol yarı sıralı
            if nums[left] <= nums[mid]:
                if nums[left] <= target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            # Sağ yarı sıralı
            else:
                if nums[mid] < target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1
        
        return -1

        

Complexity

• Time complexity (Zaman Karmaşıklığı) : O(log n), burada n dizinin uzunluğudur. İkili arama, her adımda arama alanını yarıya indirdiği için logaritmik zaman karmaşıklığına sahiptir.
• Space complexity (Alan Karmaşıklığı) : O(1), çünkü ekstra bir alan kullanılmaz, tüm işlemler mevcut dizide yapılır.