CP #14 : Search in Rotated Sorted Array Problemi

 Problem surada.

Cozum

Normalde naive implementasyon ile basliyoruz ancak burada cozum zaten direk O(n). Yani biz verilen arrayin sorted ve rotated oldugunu gozardi edip direk itere etsek zaten istenen indexi O(n) ile buluruz. O zaman naive implementasyona gerek yok. 

Follow-up'ta sorulan noktaya geleleim ve istenen indexi O(log n) ile bulmaya calisalim. O(log n)'den de anlasilacagi gibi cozum binary search'te yatiyor. Ama bir farkla, arrayin rotated olmasini nasil handle edecegiz? 

Once rotation noktasini bulup sonra binary search yapsak, islem tekrar O(n)'e gidebilir. O zaman binary search icerisinde bunu handle etmemiz gerekiyor. Her bir adimda arrayin bir notkasindan ikiye bolecegiz. Tam bu noktada rotation olup olmadigina bakabiliriz. 

1. Binary search icerisinde rotation point olmadigina bakma fikri ise yaramadi. Cunku binary search'te mid pointi aldiktan sonra sol parcayi ya da sag parcayi alip devam etmemiz gerekiyor. Bu noktada rotation yok ise, rotation'un oldugu parcayi birakip hic bir zaman bulamayabiliyoruz. 

2. Oncelikle rotatasyon noktasini binary search ile bulacagiz. Bunun icin sifirinci elemandan daha kucuk ilk elemanin oldugu indexi arayacagiz. Cunku eger rotasyon varsa array icerisinde, bir yerde sifirnci elemandan daha kucuk bir eleman bulunacaktir. Biraz modifiyeli bir binary search ile bunu yapabiliriz. 

3. Rotasyon noktasini bulduktan sonra, bunu da hesaba katacak bir binary search yazilabilir ama karmasik olur. Onun yerine, rotasyon noktasindan iki farkli binary search baslatip, target'i bulacagiz. 

Bu sayede toplamda yine O(log n) kompleksiteye sahip bir cozumumuz olacak. O zaman ilk once rotasyon noktasini bulmayla baslayalim:

def rot_point(arr, start, end):

    # base-case'imiz
    # eger elde tek bir eleman kaldiysa artik karar ani gelmis demektir

    if end-start == 0:

        # rotasyon birinci elemandan sonra gerceklesmis olabilir

        # [3, 1, 2] gibi. 

        if arr[start] == arr[0]:

            return start

        

        # eger elde kalan eleman arrayin ilk elemanindan kucukse

        # rotasyon noktasi burasi demektir

        # degilse, rotasyon noktasi yoktur, -1 dondurelim

        return start-1 if arr[start] < arr[0] else -1

    # orta notkayi buluyoruz

    mid = start + (end-start) // 2

    # eger orta noktadaki eleman

    # ilk elemandan buyuk ise, demek ki daha rotasyon noktasina gelmedik

    # demek ki rotasyon noktasi sag taraftaki kisimda

    if arr[0] < arr[mid]:

        return rot_point(arr, mid+1, end)

    else:

        return rot_point(arr, start, mid)

Bu sekilde modifiyeli bir binary search ile rotasyon noktasini O(log n) ile bulabiliyoruz. 

Simdi geldik binary search kismina. Burasi goreceli olarak daha kolay cunku bilgimiz binary search.

def bin_ser(arr, t, start, end):

    # base case kontrolu, elde tek eleman kalmis

    # eger bu eleman target'e esit ise, bulduk demektir

    # degilse arrayda yoktur, -1 dondurelim

    if end-start == 0:

        return start if arr[start] == t else -1

    

    # orta nokta

    mid = start + (end - start) // 2

    

    # eger orta nokta aranan eleman ise direk 

    # indeksi dondurelim

    if arr[mid] == target:

        return mid

    

    # bu noktada arr sorted oldugu icin 

    # eger orta nokta degeri aranan degerden kucukse

    # aradigimiz sag tarafta demektir

    if arr[mid] < target:

        # sag taraf ile devam et

        return bin_ser(arr, t, mid+1, end)

    else:

        # eger orta eleman aranandan buyukse

        # aradigimiz sol tarafta demektir

        # sol taraf ile devam et

        return bin_ser(arr, t, start, mid)

Bu sekilde de, sorted bir array icerisinde aranan bir elemani O(log n) ile bulabiliyoruz. Neden? Cunku her adimda verilen arrayin yarisi ile yola devam ediyoruz. Her adimda input yari yariya azaliyor. 

Son olarak da, genel akisi olusturalim. Verilen array icerisinde rotasyon noktasini bulacagiz, bu noktanin solu ve sagi icin iki binary search calistiracagiz. Cunku bu noktanin solu ve sagi birer sorted array. Daha sonra da max degeri dondururuz. 

# rotasyon noktasini bulalim

rot = rot_point(nums, 0, len(nums)-1)

# eger rotasyon noktasi var ise, iki farkli 

# binary search ile aramayi yapalim

if rot > -1:

    left = bin_ser(nums, target, 0, rot)

    right = bin_ser(nums, target, rot+1, len(nums)-1)

    return max(left, right)

else:

    # rotasyon yok ise direk komple array icerisinde arama yapabiliriz

    return bin_ser(nums, target, 0, len(nums)-1)

Bu haliyle leetcode'a gonderdigimde oldukca performansli oldugunu gordum, python gonderilerinin %92'sinden daha hizli bir cozum elde ettik. 

Itiraf etmem gerekiyor ki edge-case'leri handle etmek bir sure (yaklasin 2-2.5 saat kadar) zamanimi aldi. Ama burada esas onemli olan genel akis mantigini kurabilmekti. Binary search ve uygulanisini anlamak icin muazzam bir problem bence. 

Diger bir problemde gorusmek uzere, stay hungry, stay foolish, stay healthy :)