Search in Rotated Sorted Array

आपको आरोही क्रम(ascending order) में sort किए गए पूर्णांक(distinct integer) array दे रखी है और integer target दे रखा हैं।

अब मान लेते हैं की इस array को हमने किसी इंडेक्स से rotate कर दिया जैसे की :

intial array : [0,1,2,4,5,6,7] रोटेट करने का बाद हमारा array ऐसे हो गया : [4,5,6,7,0,1,2]

अब हमें rotated array में टारगेट एलिमेंट को ढूंढ़ना है । अगर टारगेट एलिमेंट नहीं मिलता है तो -1 return करना है ।

हम आपको recommend करते हैं की अगर आपने ये question अभी तक try नहीं किया है तो पहले इसे try कर लें।फिर solution देखें।

Search in Rotated Sorted Array – Approach 1:

चूँकि array sorted था but हमने उसे रोटेट कर दिया किसी element से। हम जानते हैं array सॉर्टेड था तो इस rotated array में एक ऐसा पॉइंट होगा जहाँ किसी element का next element उससे छोटा होगा। वही हमारा pivot index होगा। तो अगर हमें pivot index मिल जाता है तो हम array को उस pivot index से दो भागों में डिवाइड कर सकते हैं। फिर उन दोनों sub-array पर binary search लगा सकते हैं।

Complexity Analysis:

• Time Complexity: O(log n).
  Binary search algorithm n elements में एक element को सर्च करने में O(logn) टाइम लेता है। इसलिए इसकी टाइम ऑफ़ कम्प्लेक्सिटी (TOC) = O(logn)
• Space Complexity: O(1), क्योंकि हमने कोई extra memory allot नहीं की है.

Search in Rotated Sorted Array – Approach 2:

हमने पहले approach में जाना की array को दो भाग में divide करने पर हमें दो बार बाइनरी सर्च लगाना पड़ रहा है। इसलिए हमें अपने solution को further improve करने की जरूरत है। Interviewer आपसे code improve करने को बोलेगा। पहले approach में हम क्या improve कर सकते हैं? जाहिर है हमें एक बाइनरी सर्च में ही एलिमेंट सर्च करना चाहिए।

Logic:

• middle point = (l+r)/2 (Note: l = left index, r = right index)
• If हमें टारगेट मिड पॉइंट पर ही मिल जाता है तो mid point return क्र दो: return mid
• Else if arr[ l…mid] sorted है:
  • If target >= arr[ l ] && target <= arr[mid]
    • binarySearch from l to mid
  • Else binarySearch from mid+1 to r
• Else arr[mid…h] sorted अवश्य होगा
  • If target >= arr[mid] && target <= arr[r]
    • binarySearch from mid+1 to r
  • Else binarySearch from l to mid-1

Code:

class Solution {
    public int search(int[] nums, int target) {
        return this.binarySearchApproach1(nums,target,nums.length);
       //return this.binarySearchApproach2(nums,target,0,nums.length-1);
    }
    
    public int binarySearch(int arr[], int l, int r, int target) 
    { 
        if (r < l) 
            return -1; 
  
       /* l + (r - l)/2; */
        int mid = (l + r) / 2;  //mid point
        if (target == arr[mid]) 
            return mid; 
        if (target > arr[mid]) 
            return binarySearch(arr, (mid + 1), r, target); 
        return binarySearch(arr, l, (mid - 1), target); 
    } 
    
    public int binarySearchFindPivot(int[] arr, int l, int r) {
        // base cases 
        if (r < l) 
            return -1; 
        if (l == r) 
            return l; 
  
        /* l + (r - l)/2; */
        int mid = (l + r) / 2; 
        if (mid < r && arr[mid] > arr[mid + 1]) 
            return mid; 
        if (mid > l && arr[mid] < arr[mid - 1]) 
            return (mid - 1); 
        if (arr[l] >= arr[mid]) 
            return binarySearchFindPivot(arr, l, mid - 1); 
        return binarySearchFindPivot(arr, mid + 1, r); 
    }
    
    public int binarySearchApproach1(int[] arr, int target, int n) 
    { 
        int pivot = this.binarySearchFindPivot(arr, 0, n - 1); 
  
        // अगर हमें pivot index नहीं मिलता तो इसका मतलब array rotated नहीं है  
        if (pivot == -1) 
            return this.binarySearch(arr, 0, n - 1, target); 
  
        //अगर हमें pivot index मिल जाता है तो पहले pivot index
        // से compare करो नहीं तो subarray में सर्च करो 
        if (arr[pivot] == target) 
            return pivot; 
        if (arr[0] <= target) 
            return this.binarySearch(arr, 0, pivot - 1, target); 
        return this.binarySearch(arr, pivot + 1, n - 1, target); 
    } 
    
    public int binarySearchApproach2(int[] arr, int target, int l, int r) {
        if (r<l) {
            return -1;
        }
        int mid = (r+l)/2;
        if (arr[mid] ==  target) {
            return mid;
        }
        if (arr[l] <= arr[mid]) {
            if (target >= arr[l] && target <= arr[mid]) {
                return binarySearchApproach2(arr,target,l,mid-1);
            } else {
                return binarySearchApproach2(arr,target,mid+1,r);
            }
        }
        else {
            if (target >= arr[mid] && target <= arr[r]) {
                return binarySearchApproach2(arr,target,mid+1,r);
            } else {
                return binarySearchApproach2(arr,target,l,mid-1);
            }
        }
    }
}

Next topic