Leetcode 704 Binary Search

Soru

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

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

Örnek 1

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4

Örnek 2

Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1

Çözüm

• Sıralı bir tam sayı dizisinde belirli bir hedef değeri ikili arama (binary search) algoritması kullanarak bulmanızı ister. Bu algoritma, sıralı dizilerdeki arama işlemlerini hızlandırmak için kullanılır ve arama sürecinde dizinin yarısını her adımda atlayarak çalışır.
• Girdi: Bir 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 algoritmasını uygulayarak çözülür. İkili arama, bir başlangıç ve bir bitiş işaretçisi kullanarak, her adımda aranan değerin ortanca değere göre konumunu belirler ve arama alanını yarıya indirir.
• Çalışma Mekanizması:
• Başlangıç ve Bitiş İşaretçileri: left ve right işaretçileri dizinin başlangıç ve bitiş noktalarını belirler.
• Ortanca Değerin Belirlenmesi: Her adımda, ortanca değer (mid) hesaplanır.
• Karşılaştırma ve İşaretçilerin Güncellenmesi: Eğer mid ile gösterilen değer hedefe eşitse, arama başarılıdır ve mid döndürülür.Eğer hedef mid’den büyükse, left işaretçisi mid + 1 olarak güncellenir; eğer hedef mid’den küçükse, right işaretçisi mid - 1 olarak güncellenir.
• Sonuç: Eğer left işaretçisi right işaretçisini geçerse, hedef değer dizide yoktur ve -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 - left) // 2  # Taşma riskini azaltmak için bu şekilde hesaplanır
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        
        return -1

Complexity

• Time complexity (Zaman Karmaşıklığı) : O(log n), burada n nums dizisinin 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ü algoritma sabit miktarda ekstra alan kullanır.