Element K Position

Find the position of a given element k in a rotated sorted array

#include<vector>
using namespace std;

// Function to find the pivot index where the array is rotated
int getPivot(vector<int>& arr, int n) {
    int s = 0;             // Initialize start index (s)
    int e = n - 1;         // Initialize end index (e)
    int mid = s + (e - s) / 2;  // Calculate the middle index

    // Binary search loop to find the pivot
    while (s < e) {
        if (arr[mid] >= arr[0]) {  // If middle element is greater than or equal to the first element
            s = mid + 1;           // Move start to the right (pivot is to the right)
        } else {                   // If middle element is smaller than the first element
            e = mid;               // Move end to the left (pivot is to the left)
        }
        mid = s + (e - s) / 2;     // Recalculate the middle index
    }
    return s;  // When start and end converge, start will be the pivot index
}

// Function to perform binary search on a portion of the array
int binarySearch(vector<int>& arr, int s, int e, int key) {
    int start = s;                  // Initialize the start index
    int end = e;                    // Initialize the end index
    int mid = start + (end - start) / 2;  // Calculate the middle index

    // Binary search loop
    while (start <= end) {
        if (arr[mid] == key) {       // If middle element is equal to the key
            return mid;              // Return the index of the key
        }
        if (key > arr[mid]) {        // If key is greater than the middle element
            start = mid + 1;         // Move to the right half
        } else {                     // If key is smaller than the middle element
            end = mid - 1;           // Move to the left half
        }
        mid = start + (end - start) / 2;  // Recalculate the middle index
    }
    return -1;  // Return -1 if the key is not found
}

// Main function to find the position of the element k
int findPosition(vector<int>& arr, int n, int k) {
    int pivot = getPivot(arr, n);    // Find the pivot index where the array is rotated

    // If the key lies between the pivot and the last element, search the second half of the array
    if (k >= arr[pivot] && k <= arr[n - 1]) {
        return binarySearch(arr, pivot, n - 1, k);
    }
    // If the key lies in the first half of the array, search the first half
    else {
        return binarySearch(arr, 0, pivot - 1, k);
    }
}

Example

Array = {7, 9, 1, 2, 3}, Key = 2

1. Finding the Pivot:

   • arr = {7, 9, 1, 2, 3}, n = 5.
   • Initial state: s = 0, e = 4, mid = (0 + 4) / 2 = 2 → arr[mid] = 1.
   • Since arr[mid] < arr[0], move e = mid = 2.
   • Next iteration: s = 0, e = 2, mid = (0 + 2) / 2 = 1 → arr[mid] = 9.
   • Since arr[mid] >= arr[0], move s = mid + 1 = 2.
   • Now, s = e = 2, the pivot index is 2.

2. Binary Search:

   • Now that the pivot is 2, check where the key 2 lies:
   • Since k = 2 is between arr[pivot] = 1 and arr[n - 1] = 3, perform binary search in the range pivot to n - 1.
   • Perform binary search on arr = {1, 2, 3}:
   • Initial state: s = 2, e = 4, mid = (2 + 4) / 2 = 3 → arr[mid] = 2.
   • Since arr[mid] == k, return mid = 3.

Output

For the input arr = {7, 9, 1, 2, 3} and k = 2, the function returns 3 because 2 is at index 3 in the array.

Logic

1. getPivot:
   • The pivot is found using binary search. If the middle element is greater than or equal to the first element, the pivot is in the right half; otherwise, it is in the left half.
2. binarySearch:
   • After finding the pivot, the appropriate half of the array is searched using binary search. If the key lies between the pivot and the last element, search the right half; otherwise, search the left half.