binary.cpp

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;

// Function to find the Kth element in a
// sorted and rotated array at random point
int findkthElement(vector<int> arr, int n, int K)
{
	
	// Set the boundaries for binary search
	int l = 0;
	int h = n - 1, r;

	// Apply binary search to find R
	while (l + 1 < h)
	{
		
		// Initialize the middle element
		int mid = (l + h) / 2;
		
		// Check in the right side of mid
		if (arr[l] >= arr[mid])
			l = mid;
			
		// Else check in the left side
		else
			h = mid;
	}
	
	// Random point either l or h
	if (arr[l] < arr[h])
		r = l;
	else
		r = h;
	
	// Return the kth smallest element
	if (K <= r + 1)
		return arr[r + 1 - K];
	else
		return arr[n - (K - (r + 1))];
}

// Driver Code
int main()
{
	
	// Given Input
	vector<int> arr = { 10, 8, 6, 5, 2, 1, 13, 12 };
	int n = arr.size();
	int K = 3;
	
	// Function Call
	cout << findkthElement(arr, n, K);
}

// This code is contributed by mohit kumar 29