Given a sorted and rotated array arr[] of n unique entries, the goal is to locate the index of specified key in the array. Return -1 should the key not be found in the array.
Examples
Input : arr[] = {4, 5, 6, 7, 0, 1, 2}, key = 0
Output : 4
Input : arr[] = { 4, 5, 6, 7, 0, 1, 2 }, key = 3
Output : -1
Input : arr[] = {50, 10, 20, 30, 40}, key = 10
Output : 1Using Two Binary Searches
For instance, the min in {4, 5, 6, 7, 0, 1, 2} is 0 at index 4. Find the pivot point—or index of the min element. And at index 1 the min of 50, 10, 20, 30, 40 equals 10. How to get the min’s index? We have covered in great length here.
Once we identify the pivot, we may readily split the provided array into two sorted subarrays with the index of the min. For instance {{4, 5, 6, 7, 0, 1, 2} as {{4, 5, 6, 7}, {1, 2}} and {{50, 10, 20, 30, 40} as {{50}, {10, 20, 30, 40} }. The following are the arising cases:
Should the provided key match minimal, we return
Should min index be zero, the entire array is sorted; hence, we use binary search over the complete array.
How then should we choose the subarray in other circumstances? To call binary search for both sides, one basic concept is We can save one binary search even though the general time complexity will remain O(Log n). One intends to match the given key with the first element. For instance {{4, 5, 6, 7}, {1, 2}, and with a key = 6. We conduct binary search in the first subarray if key is more than equal to the first element; else, in the second.
C++
#include <bits/stdc++.h>
using namespace std;
// An iterative binary search function.
int binarySearch(vector<int> &arr, int low, int high, int x) {
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == x) return mid;
if (arr[mid] < x) low = mid + 1;
else high = mid - 1;
}
return -1;
}
// Function to get pivot. For array 3, 4, 5, 6, 1, 2
// it returns 4 (index of 1)
int findPivot(vector<int> &arr, int low, int high) {
while (low < high) {
// The current subarray is already sorted,
// the minimum is at the low index
if (arr[low] <= arr[high])
return low;
int mid = (low + high) / 2;
// The right half is not sorted. So
// the minimum element must be in the
// right half.
if (arr[mid] > arr[high])
low = mid + 1;
// The right half is sorted. Note that in
// this case, we do not change high to mid - 1
// but keep it to mid. The mid element
// itself can be the smallest
else
high = mid;
}
return low;
}
// Searches an element key in a pivoted
// sorted array arr of size n
int pivotedBinarySearch(vector<int> &arr, int n, int key) {
int pivot = findPivot(arr, 0, n - 1);
// If the minimum element is present at index
// 0, then the whole array is sorted
if (pivot == 0)
return binarySearch(arr, 0, n - 1, key);
// If we found a pivot, then first compare with pivot
// and then search in two subarrays around pivot
if (arr[pivot] == key)
return pivot;
if (arr[0] <= key)
return binarySearch(arr, 0, pivot - 1, key);
return binarySearch(arr, pivot + 1, n - 1, key);
}
// Driver program to check above functions
int main() {
// Let us search 3 in below array
vector<int> arr = {5, 6, 7, 8, 9, 10, 1, 2, 3};
int key = 3;
cout << pivotedBinarySearch(arr, arr.size(), key);
return 0;
}
Java
import java.util.Arrays;
public class Main {
// An iterative binary search function.
public static int binarySearch(int[] arr, int low, int high, int x) {
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == x) return mid;
if (arr[mid] < x) low = mid + 1;
else high = mid - 1;
}
return -1;
}
// Function to get pivot. For array 3, 4, 5, 6, 1, 2
// it returns 4 (index of 1)
public static int findPivot(int[] arr, int low, int high) {
while (low < high) {
// The current subarray is already sorted,
// the minimum is at the low index
if (arr[low] <= arr[high])
return low;
int mid = (low + high) / 2;
// The right half is not sorted. So
// the minimum element must be in the
// right half.
if (arr[mid] > arr[high])
low = mid + 1;
// The right half is sorted. Note that in
// this case, we do not change high to mid - 1
// but keep it to mid. The mid element
// itself can be the smallest
else
high = mid;
}
return low;
}
// Searches an element key in a pivoted
// sorted array arr of size n
public static int pivotedBinarySearch(int[] arr, int n, int key) {
int pivot = findPivot(arr, 0, n - 1);
// If the minimum element is present at index
// 0, then the whole array is sorted
if (pivot == 0)
return binarySearch(arr, 0, n - 1, key);
// If we found a pivot, then first compare with pivot
// and then search in two subarrays around pivot
if (arr[pivot] == key)
return pivot;
if (arr[0] <= key)
return binarySearch(arr, 0, pivot - 1, key);
return binarySearch(arr, pivot + 1, n - 1, key);
}
// Driver program to check above functions
public static void main(String[] args) {
// Let us search 3 in below array
int[] arr = {5, 6, 7, 8, 9, 10, 1, 2, 3};
int key = 3;
System.out.println(pivotedBinarySearch(arr, arr.length, key));
}
}Python
def binary_search(arr, low, high, x):
# An iterative binary search function.
while low <= high:
mid = low + (high - low) // 2
if arr[mid] == x:
return mid
if arr[mid] < x:
low = mid + 1
else:
high = mid - 1
return -1
def find_pivot(arr, low, high):
# Function to get pivot. For array 3, 4, 5, 6, 1, 2 it returns 4 (index of 1)
while low < high:
# The current subarray is already sorted, the minimum is at the low index
if arr[low] <= arr[high]:
return low
mid = (low + high) // 2
# The right half is not sorted. So the minimum element must be in the right half.
if arr[mid] > arr[high]:
low = mid + 1
# The right half is sorted. Note that in this case, we do not change high to mid - 1
# but keep it to mid. The mid element itself can be the smallest
else:
high = mid
return low
def pivoted_binary_search(arr, n, key):
#Searches an element key in a pivoted sorted array arr of size n
pivot = find_pivot(arr, 0, n - 1)
# If the minimum element is present at index 0, then the whole array is sorted
if pivot == 0:
return binary_search(arr, 0, n - 1, key)
# If we found a pivot, then first compare with pivot and then search in two subarrays around pivot
if arr[pivot] == key:
return pivot
if arr[0] <= key:
return binary_search(arr, 0, pivot - 1, key)
return binary_search(arr, pivot + 1, n - 1, key)
# Driver program to check above functions
if __name__ == "__main__":
# Let us search 3 in below array
arr = [5, 6, 7, 8, 9, 10, 1, 2, 3]
key = 3
print(pivoted_binary_search(arr, len(arr), key))C#
using System;
class Program {
// An iterative binary search function.
static int BinarySearch(int[] arr, int low, int high, int x) {
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == x) return mid;
if (arr[mid] < x) low = mid + 1;
else high = mid - 1;
}
return -1;
}
// Function to get pivot. For array 3, 4, 5, 6, 1, 2
// it returns 4 (index of 1)
static int FindPivot(int[] arr, int low, int high) {
while (low < high) {
// The current subarray is already sorted,
// the minimum is at the low index
if (arr[low] <= arr[high])
return low;
int mid = (low + high) / 2;
// The right half is not sorted. So
// the minimum element must be in the
// right half.
if (arr[mid] > arr[high])
low = mid + 1;
// The right half is sorted. Note that in
// this case, we do not change high to mid - 1
// but keep it to mid. The mid element
// itself can be the smallest
else
high = mid;
}
return low;
}
// Searches an element key in a pivoted
// sorted array arr of size n
static int PivotedBinarySearch(int[] arr, int n, int key) {
int pivot = FindPivot(arr, 0, n - 1);
// If the minimum element is present at index
// 0, then the whole array is sorted
if (pivot == 0)
return BinarySearch(arr, 0, n - 1, key);
// If we found a pivot, then first compare with pivot
// and then search in two subarrays around pivot
if (arr[pivot] == key)
return pivot;
if (arr[0] <= key)
return BinarySearch(arr, 0, pivot - 1, key);
return BinarySearch(arr, pivot + 1, n - 1, key);
}
// Driver program to check above functions
static void Main(string[] args) {
// Let us search 3 in below array
int[] arr = {5, 6, 7, 8, 9, 10, 1, 2, 3};
int key = 3;
Console.WriteLine(PivotedBinarySearch(arr, arr.Length, key));
}
}JavaScript
// An iterative binary search function.
function binarySearch(arr, low, high, x) {
while (low <= high) {
let mid = low + Math.floor((high - low) / 2);
if (arr[mid] === x) return mid;
if (arr[mid] < x) low = mid + 1;
else high = mid - 1;
}
return -1;
}
// Function to get pivot. For array 3, 4, 5, 6, 1, 2
// it returns 4 (index of 1)
function findPivot(arr, low, high) {
while (low < high) {
// The current subarray is already sorted,
// the minimum is at the low index
if (arr[low] <= arr[high])
return low;
let mid = Math.floor((low + high) / 2);
// The right half is not sorted. So
// the minimum element must be in the
// right half.
if (arr[mid] > arr[high])
low = mid + 1;
// The right half is sorted. Note that in
// this case, we do not change high to mid - 1
// but keep it to mid. The mid element
// itself can be the smallest
else
high = mid;
}
return low;
}
// Searches an element key in a pivoted
// sorted array arr of size n
function pivotedBinarySearch(arr, n, key) {
let pivot = findPivot(arr, 0, n - 1);
// If the minimum element is present at index
// 0, then the whole array is sorted
if (pivot === 0)
return binarySearch(arr, 0, n - 1, key);
// If we found a pivot, then first compare with pivot
// and then search in two subarrays around pivot
if (arr[pivot] === key)
return pivot;
if (arr[0] <= key)
return binarySearch(arr, 0, pivot - 1, key);
return binarySearch(arr, pivot + 1, n - 1, key);
}
// Driver program to check above functions
function main() {
// Let us search 3 in below array
const arr = [5, 6, 7, 8, 9, 10, 1, 2, 3];
const key = 3;
console.log(pivotedBinarySearch(arr, arr.length, key));
}
main();