Code Studio question

[pratik.rajput17]

Hi, Can you solve and explain this coding ninja question? (With O(log n) time complexity)

https://www.naukri.com/code360/problems/search-in-rotated-sorted-array_1082554

 

[SajalJha]

Hi, Can you solve and explain this coding ninja question? (With O(log n) time complexity)

https://www.naukri.com/code360/problems/search-in-rotated-sorted-array_1082554

The logic follows the binary search approach :-

Steps: -​

1. Set two pointers: low at the start of the array and high at the end.
2. Find the middle element.
3. Check if the middle element matches k. If yes, return the index.
4. If not, determine which side of the array is sorted (either the left half or the right half):
   • If the left half is sorted and k lies in that range, adjust high to mid - 1.
   • If the right half is sorted and k lies in that range, adjust low to mid + 1.
5. Continue adjusting low and high until you find k or conclude that k is not present in the array (when low exceeds high).

int search(vector<int>& arr, int k) {

    int low = 0, high = arr.size() - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;

        // Check if the middle element is the target
        if (arr[mid] == k) {
            return mid;
        }

        // Determine which part is sorted
        if (arr[low] <= arr[mid]) {  // Left part is sorted
            
            if (arr[low] <= k && k < arr[mid]) {
                high = mid - 1;  // Target is in the left sorted part
            }
            else {
                low = mid + 1;   // Target is in the right part
            }
        }
        else {  // Right part is sorted
            if (arr[mid] < k && k <= arr[high]) {
                low = mid + 1;   // Target is in the right sorted part
            }
            else {
                high = mid - 1;  // Target is in the left part
            }
        }
    }

    return -1;  // If the element is not found
}

 

[pratik.rajput17]

Thanks!<3