You are given a sorted array and a key element as input. Find the index of the key element in the array.
Example 1:
Input: arr[] = {5, 6, 7, 8, 9, 10, 1, 2, 3}
Key = 3
Output: Element Found at 8 index
Example 2:
Input: arr[] = {30, 40, 50, 10, 20}
Key = 10
Output: Element Found at 3 index
Approach 1: Binary Search
In this approach, we will find the mid of the array first. Then we will consider the array as two sub-arrays, divided in the mid, and search for the element in both parts.
Algorithm
- Find the index of the pivot element.
- Search the index of the element in a sorted rotated array, using the pivot element
- The array is not rotated if the pivot is not found.
- Otherwise, check if the pivot element matches the key.
- Search in the first part of the array
- If not found, search in the other part of the array.
- If found, return the element.
The implementation of the above-discussed approach is:
CPP
#include <bits/stdc++.h>
using namespace std;
// function to implement the
// binary search
int binarySearch(int arr[], int low,
int high, int key)
{
if (high < low)
return -1;
int mid = (low + high) / 2;
if (key == arr[mid])
return mid;
if (key > arr[mid])
return binarySearch(arr, (mid + 1), high, key);
return binarySearch(arr, low, (mid - 1), key);
}
// function to find
// the index of the pivot element
int searchPivotElement(int arr[], int low, int high)
{
// base cases
if (high < low)
return -1;
if (high == low)
return low;
int mid = (low + high) / 2;
if (mid < high && arr[mid] > arr[mid + 1])
return mid;
if (mid > low && arr[mid] < arr[mid - 1])
return (mid - 1);
if (arr[low] >= arr[mid])
return searchPivotElement(arr, low, mid - 1);
return searchPivotElement(arr, mid + 1, high);
}
// function to search
// the index of the element
// in a sorted rotated array,
// using the pivot element
int findElement(int arr[], int n, int key)
{
int pivot = searchPivotElement(arr, 0, n - 1);
// array is not rotated,
// if pivot is not found
if (pivot == -1)
return binarySearch(arr, 0, n - 1, key);
// otherwise, check if pivot element
// matches with the key
if (arr[pivot] == key)
return pivot;
// search in the first part of the array
// array is divided around the pivot
if (arr[0] <= key)
return binarySearch(arr, 0, pivot - 1, key);
// search in the other part of the array.
return binarySearch(arr, pivot + 1, n - 1, key);
}
int main()
{
int arr1[] = { 5, 6, 7, 8, 9, 10, 1, 2, 3 };
int n = sizeof(arr1) / sizeof(arr1[0]);
int key = 3;
cout << "Element found at the index: "
<< findElement(arr1, n, key);
cout << "\n\n";
return 0;
}
Output
Element found at the index: 8
JAVA
class Main {
// function to search
// the index of the element
// in a sorted rotated array,
// using the pivot element
static int findElement(int arr[], int n, int key)
{
int pivot = searchPivotElement(arr, 0, n - 1);
// array is not rotated,
// if pivot is not found
if (pivot == -1)
return binarySearch(arr, 0, n - 1, key);
// otherwise, check if pivot element
// matches with the key
if (arr[pivot] == key)
return pivot;
// search in the first part of the array
// array is divided around the pivot
if (arr[0] <= key)
return binarySearch(arr, 0, pivot - 1, key);
// search in the other part of the array.
return binarySearch(arr, pivot + 1, n - 1, key);
}
// function to find
// the index of the pivot element
static int searchPivotElement(int arr[], int low, int high)
{
// base cases
if (high < low)
return -1;
if (high == low)
return low;
int mid = (low + high) / 2;
if (mid < high && arr[mid] > arr[mid + 1])
return mid;
if (mid > low && arr[mid] < arr[mid - 1])
return (mid - 1);
if (arr[low] >= arr[mid])
return searchPivotElement(arr, low, mid - 1);
return searchPivotElement(arr, mid + 1, high);
}
// function to implement the
// binary search
static int binarySearch(int arr[], int low, int high, int key)
{
if (high < low)
return -1; int mid = (low + high) / 2;
if (key == arr[mid])
return mid;
if (key > arr[mid])
return binarySearch(arr, (mid + 1), high, key);
return binarySearch(arr, low, (mid - 1), key);
}
public static void main(String args[])
{
int arr1[] = { 5, 6, 7, 8, 9, 10, 1, 2, 3 };
int n = arr1.length;
int key = 3;
System.out.println("Element found at the index: "
+ findElement(arr1, n, key));
System.out.print("\n");
}
}
Output
Element found at the index: 8
Python
# function to search
# the index of the element
# in a sorted rotated array,
# using the pivot element
def findElement(arr, n, key):
pivot = searchPivotElement(arr, 0, n-1);
# array is not rotated,
# if pivot is not found
if pivot == -1:
return binarySearch(arr, 0, n-1, key);
# otherwise, check if pivot element
# matches with the key
if arr[pivot] == key:
return pivot
# search in the first part of the array
# array is divided around the pivot
if arr[0] <= key:
return binarySearch(arr, 0, pivot-1, key);
# search in the other part of the array.
return binarySearch(arr, pivot + 1, n-1, key);
# function to find
# the index of the pivot element
def searchPivotElement(arr, low, high):
# base cases
if high < low:
return -1
if high == low:
return low
# low + (high - low)/2;
mid = int((low + high)/2)
if mid < high and arr[mid] > arr[mid + 1]:
return mid
if mid > low and arr[mid] < arr[mid - 1]:
return (mid-1)
if arr[low] >= arr[mid]:
return searchPivotElement(arr, low, mid-1)
return searchPivotElement(arr, mid + 1, high)
# function to implement the
# binary search
def binarySearch(arr, low, high, key):
if high < low:
return -1
# low + (high - low)/2;
mid = int((low + high)/2)
if key == arr[mid]:
return mid
if key > arr[mid]:
return binarySearch(arr, (mid + 1), high,key);
return binarySearch(arr, low, (mid -1), key);
# Driver program to check above functions
# Let us search 3 in below array
arr1 = [5, 6, 7, 8, 9, 10, 1, 2, 3]
n = len(arr1)
key = 3
print("Element found at the index: ",
findElement(arr1, n, key))
print("\n")
Output
Element found at the index: 8
C#
using System;
class main {
// function to search
// the index of the element
// in a sorted rotated array,
// using the pivot element
static int findElement(int[] arr,int n, int key)
{
int pivot = searchPivotElemen(arr, 0, n - 1);
// array is not rotated,
// if pivot is not found
if (pivot == -1)
return binarySearch(arr, 0, n - 1, key);
// otherwise, check if pivot element
// matches with the key
if (arr[pivot] == key)
return pivot;
// search in the first part of the array
// array is divided around the pivot
if (arr[0] <= key)
return binarySearch(arr, 0, pivot - 1, key);
// search in the other part of the array.
return binarySearch(arr, pivot + 1, n - 1, key);
}
static int searchPivotElemen(int[] arr, int low, int high)
{
// base cases
if (high < low)
return -1;
if (high == low)
return low;
int mid = (low + high) / 2;
if (mid < high && arr[mid] > arr[mid + 1])
return mid;
if (mid > low && arr[mid] < arr[mid - 1])
return (mid - 1);
if (arr[low] >= arr[mid])
return searchPivotElemen(arr, low, mid - 1);
return searchPivotElemen(arr, mid + 1, high);
}
// function to implement the
// binary search
static int binarySearch(int[] arr, int low,int high, int key)
{
if (high < low)
return -1;
int mid = (low + high) / 2;
if (key == arr[mid])
return mid;
if (key > arr[mid])
return binarySearch(arr, (mid + 1), high, key);
return binarySearch(arr, low, (mid - 1), key);
}
public static void Main()
{
int[] arr1 = { 5, 6, 7, 8, 9, 10, 1, 2, 3 };
int n = arr1.Length;
int key = 3;
Console.Write("Element found at the index: "
+ findElement(arr1, n, key));
Console.Write("\n");
}
}
Output
Element found at the index: 8
PHP
<?php
// function to implement the
// binary search
function binarySearch($arr, $low,$high, $key)
{
if ($high < $low)
return -1; $mid = floor($low + $high) / 2;
if ($key == $arr[$mid])
return $mid;
if ($key > $arr[$mid])
return binarySearch($arr, ($mid + 1), $high, $key);
else
return binarySearch($arr, $low,($mid -1), $key);
}
function searchPivotElement($arr, $low, $high)
{
// base cases
if ($high < $low)
return -1;
if ($high == $low)
return $low;
$mid = ($low + $high)/2;
if ($mid < $high and $arr[$mid] >$arr[$mid + 1])
return $mid;
if ($mid > $low and $arr[$mid] < $arr[$mid - 1])
return ($mid - 1);
if ($arr[$low] >= $arr[$mid])
return searchPivotElement($arr, $low,$mid - 1);
return searchPivotElement($arr, $mid + 1, $high);
}
// function to search
// the index of the element
// in a sorted rotated array,
// using the pivot element
function findElement($arr, $n, $key)
{
$pivot = searchPivotElement($arr, 0, $n - 1);
// array is not rotated,
// if pivot is not found
if ($pivot == -1)
return binarySearch($arr, 0,
$n - 1, $key);
// otherwise, check if pivot element
// matches with the key
if ($arr[$pivot] == $key)
return $pivot;
// search in the first part of the array
// array is divided around the pivot
if ($arr[0] <= $key)
return binarySearch($arr, 0, $pivot - 1, $key);
// search in the other part of the array.
return binarySearch($arr, $pivot + 1, $n - 1, $key);
}
// Driver Code
$arr1 = array(5, 6, 7, 8, 9, 10, 1, 2, 3);
$n = count($arr1);
$key = 3;
echo "Element found at the index: ",
findElement($arr1, $n, $key);
echo "\n\n";
?>
Output
Element found at the index: 8
Complexity Analysis:
Time Complexity: O(log n), as BS takes log n time to find a given array in an element. Space Complexity: O(1), as we did not use any extra space.
Approach 2: Optimized Binary Search
This approach is the optimized Binary Search. Here, we will be checking if there is a sorted array or not. In the case of sorted array search in a standard way, the index of the key in both the halves. Find in the other subarray by dividing it into 2 parts in case the let is not found in the first subarray. Otherwise, if the subarray arr[l...mid] is not sorted, then arr[mid...h] will be sorted.
Algorithm
-
Check if there is a sorted subarray array arr[l...mid].
- In the case of sorted array search in a standard way, the index of the key in both the halves.
- Find in the other subarray by dividing it into 2 parts in case the let is not found in the first subarray.
- If the subarray arr[l...mid] is not sorted, then arr[mid...h] will be sorted.
- Return the index of the element.
The implementation of the above-discussed approach is:
CPP
#include <bits/stdc++.h>
using namespace std;
// function to search
// the index of the element
// in a sorted rotated array,
// using the pivot element
int findElement(int arr[], int l, int h, int key)
{
if (l > h)
return -1;
int mid = (l + h) / 2;
if (arr[mid] == key)
return mid;
//...1) if there is sorted subarray array arr[l...mid]
if (arr[l] <= arr[mid])
{
// in case of sorted array
// search in a standard way
// the index of the key
// in both the halves.
if (key >= arr[l] && key <= arr[mid])
return findElement(arr, l, mid - 1, key);
// find in the other subarray, by dividing it into 2 parts
// in case if the ley in not found in the first subarray
return findElement(arr, mid + 1, h, key);
}
//...2) if the subarray arr[l...mid]
// is not sorted, then
// arr[mid...h] will be sorted
if (key >= arr[mid] && key <= arr[h])
return findElement(arr, mid + 1, h, key);
return findElement(arr, l, mid - 1, key);
}
int main()
{
int arr[] = { 5, 6, 7, 8, 9, 10, 1, 2, 3 };
int n = sizeof(arr) / sizeof(arr[0]);
int key = 3;
int i = findElement(arr, 0, n - 1, key);
if (i != -1)
cout << "Element found at the index: " << i << "\n\n";
else
cout << "Element not found" << "\n\n";
}
Output
Element found at the index: 8
JAVA
class Main {
// function to search
// the index of the element
// in a sorted rotated array,
// using the pivot element
static int findElement(int arr[], int l, int h, int key)
{
if (l > h)
return -1;
int mid = (l + h) / 2;
if (arr[mid] == key)
return mid;
//...1) if there is sorted subarray array arr[l...mid]
if (arr[l] <= arr[mid])
{
// in case if sorted array
// search in a standard way
// the index of the key
// in both the halves.
if (key >= arr[l] && key <= arr[mid])
return findElement(arr, l, mid - 1, key);
// find in the other subarray, by dividing it into 2 parts
// in case if the ley in not found in the first subarray
return findElement(arr, mid + 1, h, key);
}
//...2) if the subarray arr[l...mid]
// is not sorted, then
// arr[mid...h] will be sorted
if (key >= arr[mid] && key <= arr[h])
return findElement(arr, mid + 1, h, key);
return findElement(arr, l, mid - 1, key);
}
public static void main(String args[])
{
int arr[] = { 5, 6, 7, 8, 9, 10, 1, 2, 3 };
int n = arr.length;
int key = 3;
int i = findElement(arr, 0, n - 1, key);
if (i != -1)
System.out.println("Element found at the index: " + i + "\n");
else
System.out.println("Element not found" + "\n");
}
}
Output
Element found at the index: 8
Python
# function to search
# the index of the element
# in a sorted rotated array,
# using the pivot element
def findElement (arr, l, h, key):
if l > h:
return -1
mid = (l + h) // 2
if arr[mid] == key:
return mid
#...1) if there is sorted subarray array arr[l...mid]
if arr[l] <= arr[mid]:
# in case if sorted array
# search in a standard way
# the index of the key
# in the both the halves.
if key >= arr[l] and key <= arr[mid]:
return findElement(arr, l, mid-1, key)
# find in the other subarray, by dividing it into 2 parts
# in case if the ley in not found in the first subarray
return findElement(arr, mid + 1, h, key)
#...2) if the subarray arr[l...mid]
# is not sorted, then
# arr[mid...h] will be sorted
if key >= arr[mid] and key <= arr[h]:
return findElement(arr, mid + 1, h, key)
return findElement(arr, l, mid-1, key)
# Driver program
arr = [5, 6, 7, 8, 9, 10, 1, 2, 3]
key = 3
i = findElement(arr, 0, len(arr)-1, key)
if i != -1:
print ("Element found at the index: % d"% i + "\n")
else:
print ("Element not found")
Output
Element found at the index: 8
C#
using System;
class main {
// function to search
// the index of the element
// in a sorted rotated array,
// using the pivot element
static int findElement(int[] arr, int l, int h,
int key)
{
if (l > h)
return -1;
int mid = (l + h) / 2;
if (arr[mid] == key)
return mid;
//...1) if there is sorted subarray array arr[l...mid]
if (arr[l] <= arr[mid])
{
// in case if sorted array
// search in a standard way
// the index of the key
// in the both the halves.
if (key >= arr[l] && key <= arr[mid])
return findElement(arr, l, mid - 1, key);
// find in the other subarray, by dividing it into 2 parts
// in case if the ley in not found in the first subarray
return findElement(arr, mid + 1, h, key);
}
//...2) if the subarray arr[l...mid]
// is not sorted, then
// arr[mid...h] will be sorted
if (key >= arr[mid] && key <= arr[h])
return findElement(arr, mid + 1, h, key);
return findElement(arr, l, mid - 1, key);
}
public static void Main()
{
int[] arr = { 5, 6, 7, 8, 9, 10, 1, 2, 3 };
int n = arr.Length;
int key = 3;
int i = findElement(arr, 0, n - 1, key);
if (i != -1)
Console.WriteLine("Element found at the index: " + i + "\n");
else
Console.WriteLine("Element not found");
}
}
Output
Element found at the index: 8
PHP
<?php
// function to search
// the index of the element
// in a sorted rotated array,
// using the pivot element
function findElement($arr, $l, $h, $key)
{
if ($l > $h) return -1;
$mid = ($l + $h) / 2;
if ($arr[$mid] == $key)
return $mid;
//...1) if there is sorted subarray array arr[l...mid]\
if ($arr[$l] <= $arr[$mid])
{
// in case if sorted array
// search in a standard way
// the index of the key
// in the both the halves.
if ($key >= $arr[$l] && $key <= $arr[$mid])
return findElement($arr, $l, $mid - 1, $key);
// find in the other subarray, by dividing it into 2 parts
// in case if the ley in not found in the first subarray
return findElement($arr, $mid + 1, $h, $key);
}
//...2) if the subarray arr[l...mid]
// is not sorted, then
// arr[mid...h] will be sorted
if ($key >= $arr[$mid] && $key <= $arr[$h])
return findElement($arr, $mid + 1, $h, $key);
return findElement($arr, $l, $mid-1, $key);
}
// Driver Code
$arr = array(5, 6, 7, 8, 9, 10, 1, 2, 3, 4);
$n = sizeof($arr);
$key = 3;
$i = findElement($arr, 0, $n-1, $key);
if ($i != -1)
echo "Element found at the index: ", floor($i), " \n\n";
else
echo "Element not found"; ?>
Output
Element found at the index: 8
Complexity Analysis:
- Time Complexity: O(log n), as BS takes log n time to find a given array in an element.
- Space Complexity: O(1), as we did not use any extra space.
Wrapping Up!
In this article, we have learned an amazing as well as easy concept. Searching for an element in a rotated sorted array is one of the most important data structure problems and is usually asked in the top interview questions as well. In this article, we have included proper examples with detailed explanations for a better understanding for you. We also learned about how we should think of a solution and then make optimizations in our code for such kinds of problems. We also discussed two well-explained approaches along with some suitable examples to solve this problem.
Also, we covered in detail how both of the approaches work and what is their significance of them. We discussed their time complexity along with a proper explanation. Different programmers prefer different languages for coding. So, we made sure that all our readers could refer to this article. That’s why this article also contains well-explained codes for all the approaches in the most popular languages along with their respective outputs attached to the article for a better understanding of a wide range of our readers.
We sincerely hope that this article has walked you through some deep and important concepts and how we should approach such kinds of problems. We surely wish you to keep up your practice and crack all the questions easily. With this, we are wrapping up this article.
Happy Learning!
People are also reading:
Leave a Comment on this Post