Posted on by Kalkicode
Code Recursion

# Find an element in a sorted and rotated array

In computer science, the problem of finding an element in a sorted and rotated array is a common challenge. The array is initially sorted in ascending order and then rotated at some pivot point, where the elements to the right of the pivot come before the elements to the left. The task is to efficiently locate a given target element in the rotated array.

## Problem Statement

Given a sorted and rotated array `arr`, we need to find the index of a target element `k` in the array. If the element is present, the algorithm should return the index of the target element; otherwise, it should return -1.

## Explanation with Example

Let's take the array `arr = [7, 8, 9, 1, 2, 3, 4, 5, 6]` as an example. The array is sorted in ascending order initially, but it has been rotated at the pivot point between 9 and 1. If we want to find the element 2, the algorithm should return index 4. Similarly, for element 9, the algorithm should return index 2.

## Pseudocode

The following is the standard pseudocode for the algorithm to find an element in a sorted and rotated array:

``````1. Function binarySearch(arr, k, low, high)
2.     If low > high
3.         Return -1
4.     Else
5.         mid = (low + high) / 2
6.         If arr[mid] == k
7.             Return mid
8.         If arr[low] < arr[mid]
9.             If k >= arr[low] AND k < arr[mid]
10.                Return binarySearch(arr, k, low, mid - 1)
11.            Else
12.                Return binarySearch(arr, k, mid + 1, high)
13.        Else If arr[mid] < arr[high]
14.            If k > arr[mid] AND k <= arr[high]
15.                Return binarySearch(arr, k, mid + 1, high)
16.            Else
17.                Return binarySearch(arr, k, low, mid - 1)
18.        Else If arr[low] == arr[mid]
19.            If arr[mid] != arr[high]
20.                Return binarySearch(arr, k, mid + 1, high)
21.            Else
22.                result = binarySearch(arr, k, low, mid - 1)
23.                If result == -1
24.                    result = binarySearch(arr, k, mid + 1, high)
25.                Return result
``````

## Algorithm Explanation

The algorithm is a variation of the binary search algorithm. It takes a sorted and rotated array `arr`, the target element `k`, and the low and high indices of the array as input. It searches for the target element `k` in the array and returns the index of the element if found, or -1 if not found.

The binarySearch function first checks if the low index is greater than the high index, which means the target element is not present, and it returns -1. Otherwise, it calculates the mid index and compares the element at the mid index with the target element `k`.

If the element at the mid index is equal to the target element `k`, it means the element is found, and the function returns the mid index.

If the element at the low index is less than the element at the mid index, it implies that the elements from `low` to `mid` are in sorted order. In this case, the algorithm checks if the target element `k` falls within this range. If it does, the algorithm performs a recursive binary search on the left half of the array (from `low` to `mid-1`); otherwise, it performs a recursive binary search on the right half of the array (from `mid+1` to `high`).

Similarly, if the element at the mid index is less than the element at the high index, it means the elements from `mid` to `high` are in sorted order. The algorithm checks if the target element `k` falls within this range and proceeds with the recursive binary search accordingly.

If the elements at both the low and mid indices are equal, it indicates that there are repeated elements in the array. The algorithm checks if the element at the mid index is different from the element at the high index to decide which side to perform the recursive binary search. If the element at the mid index is also equal to the element at the high index, it means we need to check both the left and right subtrees to find the target element.

## Program Solution

``````// C Program
// Find an element in a sorted and rotated array
#include <stdio.h>

// Display array elements
void display(int arr[], int size)
{
printf("\n\n Array Elements \n [");
for (int i = 0; i < size; ++i)
{
printf("   %d", arr[i]);
}
printf("  ]\n");
}
// Finding the element location of sorted rotated array
int binarySearch(int arr[], int k, int low, int high)
{
if (low > high)
{
return -1;
}
else
{
int mid = (low + high) / 2;
if (arr[mid] == k)
{
// When element exist
return mid;
}
if (arr[low] < arr[mid])
{
// When elements are sort in location low to mid position
if (k >= arr[low] && k < arr[mid])
{
// When the element is possible in the (low) to (mid-1) position
return binarySearch(arr, k, low, mid - 1);
}
else
{
// When the element is possible in the (mid+1) to (high) position
return binarySearch(arr, k, mid + 1, high);
}
}
else if (arr[mid] < arr[high])
{
if (k > arr[mid] && k <= arr[high])
{
// When the element is possible in the (mid+1) to (high) position
return binarySearch(arr, k, mid + 1, high);
}
else
{
// When the element is possible in the (low) to (mid-1) position
return binarySearch(arr, k, low, mid - 1);
}
}
else if (arr[low] == arr[mid])
{
// When repeated array element exists
if (arr[mid] != arr[high])
{
return binarySearch(arr, k, mid + 1, high);
}
else
{
// Check if that element exists in left subtree
int result = binarySearch(arr, k, low, mid - 1);
if (result == -1)
{
// When element not exist in left subtree then
// Check that element exists in right subtree
result = binarySearch(arr, k, mid + 1, high);
}
return result;
}
}
}
}
void findElement(int arr[], int size, int k)
{
int location = binarySearch(arr, k, 0, size - 1);
if (location == -1)
{
printf("\n Element %d Are not exist ", k);
}
else
{
printf("\n Element %d exist in location %d ", k, location);
}
}
int main()
{
// Defining sorted and rotated array of integer element
int arr1[] = {
7 , 8 , 9 , 1 , 2 , 3 , 4 , 5 , 6
};
int arr2[] = {
11 , 22 , 43 , 45 , 51 , 62 , 73 , 1 , 9 , 10
};
// Get the size
int size = sizeof(arr1) / sizeof(arr1);
display(arr1, size);
findElement(arr1, size, 9);
findElement(arr1, size, 3);
// Get the size
size = sizeof(arr2) / sizeof(arr2);
display(arr2, size);
// Test Case B (of arr2)
findElement(arr2, size, 9);
findElement(arr2, size, 11);
findElement(arr2, size, 67);
return 0;
}``````

#### Output

`````` Array Elements
[   7   8   9   1   2   3   4   5   6  ]

Element 9 exist in location 2
Element 3 exist in location 5

Array Elements
[   11   22   43   45   51   62   73   1   9   10  ]

Element 9 exist in location 8
Element 11 exist in location 0
Element 67 Are not exist``````
``````/*
Java program
Find an element in a sorted and rotated array
*/
public class SearchElement
{
// Display array elements
public void display(int[] arr, int size)
{
System.out.print("\n\n Array Elements \n [");
for (int i = 0; i < size; ++i)
{
System.out.print("   " + arr[i]);
}
System.out.print(" ]\n");
}
// Finding the element location of sorted rotated array
public int binarySearch(int[] arr, int k, int low, int high)
{
if (low > high)
{
return -1;
}
else
{
int mid = (low + high) / 2;
if (arr[mid] == k)
{
// When element exist
return mid;
}
if (arr[low] < arr[mid])
{
// When elements are sort in location low to mid position
if (k >= arr[low] && k < arr[mid])
{
// When the element is possible in the (low) to (mid-1) position
return binarySearch(arr, k, low, mid - 1);
}
else
{
// When the element is possible in the (mid+1) to (high) position
return binarySearch(arr, k, mid + 1, high);
}
}
else if (arr[mid] < arr[high])
{
if (k > arr[mid] && k <= arr[high])
{
// When the element is possible in the (mid+1) to (high) position
return binarySearch(arr, k, mid + 1, high);
}
else
{
// When the element is possible in the (low) to (mid-1) position
return binarySearch(arr, k, low, mid - 1);
}
}
else if (arr[low] == arr[mid])
{
// When repeated array element exists
if (arr[mid] != arr[high])
{
return binarySearch(arr, k, mid + 1, high);
}
else
{
// Check if that element exists in left subtree
int result = binarySearch(arr, k, low, mid - 1);
if (result == -1)
{
// When element not exist in left subtree then
// Check that element exists in right subtree
result = binarySearch(arr, k, mid + 1, high);
}
return result;
}
}
}
return -1;
}
// Handle request to find array elements
public void findElement(int[] arr, int size, int k)
{
int location = binarySearch(arr, k, 0, size - 1);
if (location == -1)
{
System.out.print("\n Element " + k + " Are not exist ");
}
else
{
System.out.print("\n Element " + k + " exist in location " + location);
}
}
public static void main(String[] args)
{
// Defining sorted and rotated array of integer element
int[] arr1 = {
7 , 8 , 9 , 1 , 2 , 3 , 4 , 5 , 6
};
int[] arr2 = {
11 , 22 , 43 , 45 , 51 , 62 , 73 , 1 , 9 , 10
};
// Get the size
int size = arr1.length;
// Test Cases
// Get the size
size = arr2.length;
// Test Cases
}
}``````

#### Output

`````` Array Elements
[   7   8   9   1   2   3   4   5   6 ]

Element 9 exist in location 2
Element 3 exist in location 5

Array Elements
[   11   22   43   45   51   62   73   1   9   10 ]

Element 9 exist in location 8
Element 11 exist in location 0
Element 67 Are not exist``````
``````// Include header file
#include <iostream>

using namespace std;
/*
C++ program
Find an element in a sorted and rotated array
*/
class SearchElement
{
public:
//  Display array elements
void display(int arr[], int size)
{
cout << "\n\n Array Elements \n [";
for (int i = 0; i < size; ++i)
{
cout << "   " << arr[i];
}
cout << " ]";
}
//  Finding the element location of sorted rotated array
int binarySearch(int arr[], int k, int low, int high)
{
if (low > high)
{
return -1;
}
else
{
int mid = (low + high) / 2;
if (arr[mid] == k)
{
//  When element exist
return mid;
}
if (arr[low] < arr[mid])
{
//  When elements are sort in location low to mid position
if (k >= arr[low] && k < arr[mid])
{
//  When the element is possible in the (low) to (mid-1) position
return this->binarySearch(arr, k, low, mid - 1);
}
else
{
//  When the element is possible in the (mid+1) to (high) position
return this->binarySearch(arr, k, mid + 1, high);
}
}
else if (arr[mid] < arr[high])
{
if (k > arr[mid] && k <= arr[high])
{
//  When the element is possible in the (mid+1) to (high) position
return this->binarySearch(arr, k, mid + 1, high);
}
else
{
//  When the element is possible in the (low) to (mid-1) position
return this->binarySearch(arr, k, low, mid - 1);
}
}
else if (arr[low] == arr[mid])
{
//  When repeated array element exists
if (arr[mid] != arr[high])
{
return this->binarySearch(arr, k, mid + 1, high);
}
else
{
//  Check if that element exists in left subtree
int result = this->binarySearch(arr, k, low, mid - 1);
if (result == -1)
{
//  When element not exist in left subtree then
//  Check that element exists in right subtree
result = this->binarySearch(arr, k, mid + 1, high);
}
return result;
}
}
}
return -1;
}
//  Handle request to find array elements
void findElement(int arr[], int size, int k)
{
int location = this->binarySearch(arr, k, 0, size - 1);
if (location == -1)
{
cout << "\n Element " << k << " Are not exist ";
}
else
{
cout << "\n Element " << k << " exist in location " << location;
}
}
};
int main()
{
//  Defining sorted and rotated array of integer element
int arr1[] = {
7 , 8 , 9 , 1 , 2 , 3 , 4 , 5 , 6
};
int arr2[] = {
11 , 22 , 43 , 45 , 51 , 62 , 73 , 1 , 9 , 10
};
//  Get the size
int size = sizeof(arr1) / sizeof(arr1);
//  Test Cases
//  Get the size
size = sizeof(arr2) / sizeof(arr2);
//  Test Cases
return 0;
}``````

#### Output

`````` Array Elements
[   7   8   9   1   2   3   4   5   6 ]
Element 9 exist in location 2
Element 3 exist in location 5

Array Elements
[   11   22   43   45   51   62   73   1   9   10 ]
Element 9 exist in location 8
Element 11 exist in location 0
Element 67 Are not exist``````
``````// Include namespace system
using System;
/*
C# program
Find an element in a sorted and rotated array
*/
public class SearchElement
{
//  Display array elements
public void display(int[] arr, int size)
{
Console.Write("\n\n Array Elements \n [");
for (int i = 0; i < size; ++i)
{
Console.Write("   " + arr[i]);
}
Console.Write(" ]");
}
//  Finding the element location of sorted rotated array
public int binarySearch(int[] arr, int k, int low, int high)
{
if (low > high)
{
return -1;
}
else
{
int mid = (low + high) / 2;
if (arr[mid] == k)
{
//  When element exist
return mid;
}
if (arr[low] < arr[mid])
{
//  When elements are sort in location low to mid position
if (k >= arr[low] && k < arr[mid])
{
//  When the element is possible in the (low) to (mid-1) position
return binarySearch(arr, k, low, mid - 1);
}
else
{
//  When the element is possible in the (mid+1) to (high) position
return binarySearch(arr, k, mid + 1, high);
}
}
else if (arr[mid] < arr[high])
{
if (k > arr[mid] && k <= arr[high])
{
//  When the element is possible in the (mid+1) to (high) position
return binarySearch(arr, k, mid + 1, high);
}
else
{
//  When the element is possible in the (low) to (mid-1) position
return binarySearch(arr, k, low, mid - 1);
}
}
else if (arr[low] == arr[mid])
{
//  When repeated array element exists
if (arr[mid] != arr[high])
{
return binarySearch(arr, k, mid + 1, high);
}
else
{
//  Check if that element exists in left subtree
int result = binarySearch(arr, k, low, mid - 1);
if (result == -1)
{
//  When element not exist in left subtree then
//  Check that element exists in right subtree
result = binarySearch(arr, k, mid + 1, high);
}
return result;
}
}
}
return -1;
}
//  Handle request to find array elements
public void findElement(int[] arr, int size, int k)
{
int location = binarySearch(arr, k, 0, size - 1);
if (location == -1)
{
Console.Write("\n Element " + k + " Are not exist ");
}
else
{
Console.Write("\n Element " + k + " exist in location " + location);
}
}
public static void Main(String[] args)
{
//  Defining sorted and rotated array of integer element
int[] arr1 = {
7 , 8 , 9 , 1 , 2 , 3 , 4 , 5 , 6
};
int[] arr2 = {
11 , 22 , 43 , 45 , 51 , 62 , 73 , 1 , 9 , 10
};
//  Get the size
int size = arr1.Length;
//  Test Cases
//  Get the size
size = arr2.Length;
//  Test Cases
}
}``````

#### Output

`````` Array Elements
[   7   8   9   1   2   3   4   5   6 ]
Element 9 exist in location 2
Element 3 exist in location 5

Array Elements
[   11   22   43   45   51   62   73   1   9   10 ]
Element 9 exist in location 8
Element 11 exist in location 0
Element 67 Are not exist``````
``````<?php
/*
Php program
Find an element in a sorted and rotated array
*/
class SearchElement
{
//  Display array elements
public	function display( & \$arr, \$size)
{
echo "\n\n Array Elements \n [";
for (\$i = 0; \$i < \$size; ++\$i)
{
echo "   ". \$arr[\$i];
}
echo " ]";
}
//  Finding the element location of sorted rotated array
public	function binarySearch( & \$arr, \$k, \$low, \$high)
{
if (\$low > \$high)
{
return -1;
}
else
{
\$mid = intval((\$low + \$high) / 2);
if (\$arr[\$mid] == \$k)
{
//  When element exist
return \$mid;
}
if (\$arr[\$low] < \$arr[\$mid])
{
//  When elements are sort in location low to mid position
if (\$k >= \$arr[\$low] && \$k < \$arr[\$mid])
{
//  When the element is possible in the (low) to (mid-1) position
return \$this->binarySearch(\$arr, \$k, \$low, \$mid - 1);
}
else
{
//  When the element is possible in the (mid+1) to (high) position
return \$this->binarySearch(\$arr, \$k, \$mid + 1, \$high);
}
}
else if (\$arr[\$mid] < \$arr[\$high])
{
if (\$k > \$arr[\$mid] && \$k <= \$arr[\$high])
{
//  When the element is possible in the (mid+1) to (high) position
return \$this->binarySearch(\$arr, \$k, \$mid + 1, \$high);
}
else
{
//  When the element is possible in the (low) to (mid-1) position
return \$this->binarySearch(\$arr, \$k, \$low, \$mid - 1);
}
}
else if (\$arr[\$low] == \$arr[\$mid])
{
//  When repeated array element exists
if (\$arr[\$mid] != \$arr[\$high])
{
return \$this->binarySearch(\$arr, \$k, \$mid + 1, \$high);
}
else
{
//  Check if that element exists in left subtree
\$result = \$this->binarySearch(\$arr, \$k, \$low, \$mid - 1);
if (\$result == -1)
{
//  When element not exist in left subtree then
//  Check that element exists in right subtree
\$result = \$this->binarySearch(\$arr, \$k, \$mid + 1, \$high);
}
return \$result;
}
}
}
return -1;
}
//  Handle request to find array elements
public	function findElement( & \$arr, \$size, \$k)
{
\$location = \$this->binarySearch(\$arr, \$k, 0, \$size - 1);
if (\$location == -1)
{
echo "\n Element ". \$k ." Are not exist ";
}
else
{
echo "\n Element ". \$k ." exist in location ". \$location;
}
}
}

function main()
{
//  Defining sorted and rotated array of integer element
\$arr1 = array(7, 8, 9, 1, 2, 3, 4, 5, 6);
\$arr2 = array(11, 22, 43, 45, 51, 62, 73, 1, 9, 10);
//  Get the size
\$size = count(\$arr1);
//  Test Cases
//  Get the size
\$size = count(\$arr2);
//  Test Cases
}
main();``````

#### Output

`````` Array Elements
[   7   8   9   1   2   3   4   5   6 ]
Element 9 exist in location 2
Element 3 exist in location 5

Array Elements
[   11   22   43   45   51   62   73   1   9   10 ]
Element 9 exist in location 8
Element 11 exist in location 0
Element 67 Are not exist``````
``````/*
Node Js program
Find an element in a sorted and rotated array
*/
class SearchElement
{
//  Display array elements
display(arr, size)
{
process.stdout.write("\n\n Array Elements \n [");
for (var i = 0; i < size; ++i)
{
process.stdout.write("   " + arr[i]);
}
process.stdout.write(" ]");
}
//  Finding the element location of sorted rotated array
binarySearch(arr, k, low, high)
{
if (low > high)
{
return -1;
}
else
{
var mid = parseInt((low + high) / 2);
if (arr[mid] == k)
{
//  When element exist
return mid;
}
if (arr[low] < arr[mid])
{
//  When elements are sort in location low to mid position
if (k >= arr[low] && k < arr[mid])
{
//  When the element is possible in the (low) to (mid-1) position
return this.binarySearch(arr, k, low, mid - 1);
}
else
{
//  When the element is possible in the (mid+1) to (high) position
return this.binarySearch(arr, k, mid + 1, high);
}
}
else if (arr[mid] < arr[high])
{
if (k > arr[mid] && k <= arr[high])
{
//  When the element is possible in the (mid+1) to (high) position
return this.binarySearch(arr, k, mid + 1, high);
}
else
{
//  When the element is possible in the (low) to (mid-1) position
return this.binarySearch(arr, k, low, mid - 1);
}
}
else if (arr[low] == arr[mid])
{
//  When repeated array element exists
if (arr[mid] != arr[high])
{
return this.binarySearch(arr, k, mid + 1, high);
}
else
{
//  Check if that element exists in left subtree
var result = this.binarySearch(arr, k, low, mid - 1);
if (result == -1)
{
//  When element not exist in left subtree then
//  Check that element exists in right subtree
result = this.binarySearch(arr, k, mid + 1, high);
}
return result;
}
}
}
return -1;
}
//  Handle request to find array elements
findElement(arr, size, k)
{
var location = this.binarySearch(arr, k, 0, size - 1);
if (location == -1)
{
process.stdout.write("\n Element " + k + " Are not exist ");
}
else
{
process.stdout.write("\n Element " + k + " exist in location " + location);
}
}
}

function main()
{
//  Defining sorted and rotated array of integer element
var arr1 = [7, 8, 9, 1, 2, 3, 4, 5, 6];
var arr2 = [11, 22, 43, 45, 51, 62, 73, 1, 9, 10];
//  Get the size
var size = arr1.length;
//  Test Cases
//  Get the size
size = arr2.length;
//  Test Cases
}
main();``````

#### Output

`````` Array Elements
[   7   8   9   1   2   3   4   5   6 ]
Element 9 exist in location 2
Element 3 exist in location 5

Array Elements
[   11   22   43   45   51   62   73   1   9   10 ]
Element 9 exist in location 8
Element 11 exist in location 0
Element 67 Are not exist``````
``````#   Python 3 program
#   Find an element in a sorted and rotated list

class SearchElement :
#   Display array elements
def display(self, arr, size) :
print("\n\n Array Elements \n [", end = "")
i = 0
while (i < size) :
print("   ", arr[i], end = "")
i += 1

print(" ]", end = "")

#   Finding the element location of sorted rotated array
def binarySearch(self, arr, k, low, high) :
if (low > high) :
return -1
else :
mid = int((low + high) / 2)
if (arr[mid] == k) :
#   When element exist
return mid

if (arr[low] < arr[mid]) :
#   When elements are sort in location low to mid position
if (k >= arr[low] and k < arr[mid]) :
#   When the element is possible in the (low) to (mid-1) position
return self.binarySearch(arr, k, low, mid - 1)
else :
#   When the element is possible in the (mid+1) to (high) position
return self.binarySearch(arr, k, mid + 1, high)

elif(arr[mid] < arr[high]) :
if (k > arr[mid] and k <= arr[high]) :
#   When the element is possible in the (mid+1) to (high) position
return self.binarySearch(arr, k, mid + 1, high)
else :
#   When the element is possible in the (low) to (mid-1) position
return self.binarySearch(arr, k, low, mid - 1)

elif(arr[low] == arr[mid]) :
#   When repeated array element exists
if (arr[mid] != arr[high]) :
return self.binarySearch(arr, k, mid + 1, high)
else :
#   Check if that element exists in left subtree
result = self.binarySearch(arr, k, low, mid - 1)
if (result == -1) :
#   When element not exist in left subtree then
#   Check that element exists in right subtree
result = self.binarySearch(arr, k, mid + 1, high)

return result

return -1

#   Handle request to find array elements
def findElement(self, arr, size, k) :
location = self.binarySearch(arr, k, 0, size - 1)
if (location == -1) :
print("\n Element ", k ," Are not exist ", end = "")
else :
print("\n Element ", k ," exist in location ", location, end = "")

def main() :
#   Defining sorted and rotated array of integer element
arr1 = [7, 8, 9, 1, 2, 3, 4, 5, 6]
arr2 = [11, 22, 43, 45, 51, 62, 73, 1, 9, 10]
#   Get the size
size = len(arr1)
#   Test Cases
#   Get the size
size = len(arr2)
#   Test Cases

if __name__ == "__main__": main()``````

#### Output

`````` Array Elements
[    7    8    9    1    2    3    4    5    6 ]
Element  9  exist in location  2
Element  3  exist in location  5

Array Elements
[    11    22    43    45    51    62    73    1    9    10 ]
Element  9  exist in location  8
Element  11  exist in location  0
Element  67  Are not exist``````
``````#  Ruby program
#  Find an element in a sorted and rotated array

class SearchElement
#   Display array elements
def display(arr, size)
print("\n\n Array Elements \n [")
i = 0
while (i < size)
print("   ", arr[i])
i += 1
end

print(" ]")
end

#   Finding the element location of sorted rotated array
def binarySearch(arr, k, low, high)
if (low > high)
return -1
else
mid = (low + high) / 2
if (arr[mid] == k)
#   When element exist
return mid
end

if (arr[low] < arr[mid])
#   When elements are sort in location low to mid position
if (k >= arr[low] && k < arr[mid])
#   When the element is possible in the (low) to (mid-1) position
return self.binarySearch(arr, k, low, mid - 1)
else
#   When the element is possible in the (mid+1) to (high) position
return self.binarySearch(arr, k, mid + 1, high)
end

elsif(arr[mid] < arr[high])
if (k > arr[mid] && k <= arr[high])
#   When the element is possible in the (mid+1) to (high) position
return self.binarySearch(arr, k, mid + 1, high)
else
#   When the element is possible in the (low) to (mid-1) position
return self.binarySearch(arr, k, low, mid - 1)
end

elsif(arr[low] == arr[mid])
#   When repeated array element exists
if (arr[mid] != arr[high])
return self.binarySearch(arr, k, mid + 1, high)
else
#   Check if that element exists in left subtree
result = self.binarySearch(arr, k, low, mid - 1)
if (result == -1)
#   When element not exist in left subtree then
#   Check that element exists in right subtree
result = self.binarySearch(arr, k, mid + 1, high)
end

return result
end

end

end

return -1
end

#   Handle request to find array elements
def findElement(arr, size, k)
location = self.binarySearch(arr, k, 0, size - 1)
if (location == -1)
print("\n Element ", k ," Are not exist ")
else
print("\n Element ", k ," exist in location ", location)
end

end

end

def main()
#   Defining sorted and rotated array of integer element
arr1 = [7, 8, 9, 1, 2, 3, 4, 5, 6]
arr2 = [11, 22, 43, 45, 51, 62, 73, 1, 9, 10]
#   Get the size
size = arr1.length
#   Test Cases
#   Get the size
size = arr2.length
#   Test Cases
end

main()``````

#### Output

``````
Array Elements
[   7   8   9   1   2   3   4   5   6 ]
Element 9 exist in location 2
Element 3 exist in location 5

Array Elements
[   11   22   43   45   51   62   73   1   9   10 ]
Element 9 exist in location 8
Element 11 exist in location 0
Element 67 Are not exist ``````
``````/*
Scala program
Find an element in a sorted and rotated array
*/
class SearchElement
{
//   Display array elements
def display(arr: Array[Int], size: Int): Unit = {
print("\n\n Array Elements \n [");
var i: Int = 0;
while (i < size)
{
print("   " + arr(i));
i += 1;
}
print(" ]");
}
//   Finding the element location of sorted rotated array
def binarySearch(arr: Array[Int], k: Int, low: Int, high: Int): Int = {
if (low > high)
{
return -1;
}
else
{
var mid: Int = ((low + high) / 2).toInt;
if (arr(mid) == k)
{
//   When element exist
return mid;
}
if (arr(low) < arr(mid))
{
//   When elements are sort in location low to mid position
if (k >= arr(low) && k < arr(mid))
{
//   When the element is possible in the (low) to (mid-1) position
return this.binarySearch(arr, k, low, mid - 1);
}
else
{
//   When the element is possible in the (mid+1) to (high) position
return this.binarySearch(arr, k, mid + 1, high);
}
}
else if (arr(mid) < arr(high))
{
if (k > arr(mid) && k <= arr(high))
{
//   When the element is possible in the (mid+1) to (high) position
return this.binarySearch(arr, k, mid + 1, high);
}
else
{
//   When the element is possible in the (low) to (mid-1) position
return this.binarySearch(arr, k, low, mid - 1);
}
}
else if (arr(low) == arr(mid))
{
//   When repeated array element exists
if (arr(mid) != arr(high))
{
return this.binarySearch(arr, k, mid + 1, high);
}
else
{
//   Check if that element exists in left subtree
var result: Int = this.binarySearch(arr, k, low, mid - 1);
if (result == -1)
{
//   When element not exist in left subtree then
//   Check that element exists in right subtree
result = this.binarySearch(arr, k, mid + 1, high);
}
return result;
}
}
}
return -1;
}
//   Handle request to find array elements
def findElement(arr: Array[Int], size: Int, k: Int): Unit = {
var location: Int = this.binarySearch(arr, k, 0, size - 1);
if (location == -1)
{
print("\n Element " + k + " Are not exist ");
}
else
{
print("\n Element " + k + " exist in location " + location);
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: SearchElement = new SearchElement();
//   Defining sorted and rotated array of integer element
var arr1: Array[Int] = Array(7, 8, 9, 1, 2, 3, 4, 5, 6);
var arr2: Array[Int] = Array(11, 22, 43, 45, 51, 62, 73, 1, 9, 10);
//   Get the size
var size: Int = arr1.length;
//   Test Cases
//   Get the size
size = arr2.length;
//   Test Cases
}
}``````

#### Output

`````` Array Elements
[   7   8   9   1   2   3   4   5   6 ]
Element 9 exist in location 2
Element 3 exist in location 5

Array Elements
[   11   22   43   45   51   62   73   1   9   10 ]
Element 9 exist in location 8
Element 11 exist in location 0
Element 67 Are not exist``````
``````/*
Swift 4 program
Find an element in a sorted and rotated array
*/
class SearchElement
{
// Display array elements
func display(_ arr: [Int], _ size: Int)
{
print("\n\n Array Elements \n [", terminator: "");
var i: Int = 0;
while (i < size)
{
print("   ", arr[i], terminator: "");
i += 1;
}
print(" ]", terminator: "");
}
// Finding the element location of sorted rotated array
func binarySearch(_ arr: [Int], _ k: Int, _ low: Int, _ high: Int)->Int
{
if (low > high)
{
return -1;
}
else
{
let mid: Int = (low + high) / 2;
if (arr[mid] == k)
{
// When element exist
return mid;
}
if (arr[low] < arr[mid])
{
// When elements are sort in location low to mid position
if (k >= arr[low] && k < arr[mid])
{
// When the element is possible in the (low) to (mid-1) position
return self.binarySearch(arr, k, low, mid - 1);
}
else
{
// When the element is possible in the (mid+1) to (high) position
return self.binarySearch(arr, k, mid + 1, high);
}
}
else if (arr[mid] < arr[high])
{
if (k > arr[mid] && k <= arr[high])
{
// When the element is possible in the (mid+1) to (high) position
return self.binarySearch(arr, k, mid + 1, high);
}
else
{
// When the element is possible in the (low) to (mid-1) position
return self.binarySearch(arr, k, low, mid - 1);
}
}
else if (arr[low] == arr[mid])
{
// When repeated array element exists
if (arr[mid] != arr[high])
{
return self.binarySearch(arr, k, mid + 1, high);
}
else
{
// Check if that element exists in left subtree
var result: Int = self.binarySearch(arr, k, low, mid - 1);
if (result == -1)
{
// When element not exist in left subtree then
// Check that element exists in right subtree
result = self.binarySearch(arr, k, mid + 1, high);
}
return result;
}
}
}
return -1;
}
// Handle request to find array elements
func findElement(_ arr: [Int], _ size: Int, _ k: Int)
{
let location: Int = self.binarySearch(arr, k, 0, size - 1);
if (location == -1)
{
print("\n Element ", k ," Are not exist ", terminator: "");
}
else
{
print("\n Element ", k ," exist in location ", location, terminator: "");
}
}
}
func main()
{
// Defining sorted and rotated array of integer element
let arr1: [Int] = [7, 8, 9, 1, 2, 3, 4, 5, 6];
let arr2: [Int] = [11, 22, 43, 45, 51, 62, 73, 1, 9, 10];
// Get the size
var size: Int = arr1.count;
// Test Cases
// Get the size
size = arr2.count;
// Test Cases
}
main();``````

#### Output

`````` Array Elements
[    7    8    9    1    2    3    4    5    6 ]
Element  9  exist in location  2
Element  3  exist in location  5

Array Elements
[    11    22    43    45    51    62    73    1    9    10 ]
Element  9  exist in location  8
Element  11  exist in location  0
Element  67  Are not exist``````
``````/*
Kotlin program
Find an element in a sorted and rotated array
*/
class SearchElement
{
//   Display array elements
fun display(arr: Array<Int>, size: Int): Unit
{
print("\n\n Array Elements \n [");
var i: Int = 0;
while (i<size)
{
print("   " + arr[i]);
i += 1;
}
print(" ]");
}
//   Finding the element location of sorted rotated array
fun binarySearch(arr: Array<Int>, k: Int, low: Int, high: Int): Int
{
if (low>high)
{
return -1;
}
else
{
var mid: Int = (low + high) / 2;
if (arr[mid] == k)
{
// When element exist
return mid;
}
if (arr[low]<arr[mid])
{
// When elements are sort in location low to mid position
if (k>= arr[low] && k<arr[mid])
{
// When the element is possible in the (low) to (mid-1) position
return this.binarySearch(arr, k, low, mid - 1);
}
else
{
// When the element is possible in the (mid+1) to (high) position
return this.binarySearch(arr, k, mid + 1, high);
}
}
else
if (arr[mid]<arr[high])
{
if (k>arr[mid] && k <= arr[high])
{
// When the element is possible in the (mid+1) to (high) position
return this.binarySearch(arr, k, mid + 1, high);
}
else
{
// When the element is possible in the (low) to (mid-1) position
return this.binarySearch(arr, k, low, mid - 1);
}
}
else
if (arr[low] == arr[mid])
{
// When repeated array element exists
if (arr[mid] != arr[high])
{
return this.binarySearch(arr, k, mid + 1, high);
}
else
{
// Check if that element exists in left subtree
var result: Int = this.binarySearch(arr, k, low, mid - 1);
if (result == -1)
{
// When element not exist in left subtree then
// Check that element exists in right subtree
result = this.binarySearch(arr, k, mid + 1, high);
}
return result;
}
}
}
return -1;
}
// Handle request to find array elements
fun findElement(arr: Array<Int>, size: Int, k: Int): Unit
{
var location: Int = this.binarySearch(arr, k, 0, size - 1);
if (location == -1)
{
print("\n Element " + k + " Are not exist ");
}
else
{
print("\n Element " + k + " exist in location " + location);
}
}
}
fun main(args: Array<String>): Unit
{
// Defining sorted and rotated array of integer element
var arr1: Array<Int> = arrayOf(7, 8, 9, 1, 2, 3, 4, 5, 6);
var arr2: Array<Int> = arrayOf(11, 22, 43, 45, 51, 62, 73, 1, 9, 10);
// Get the size
var size: Int = arr1.count();
// Test Cases
// Get the size
size = arr2.count();
// Test Cases
}``````

#### Output

`````` Array Elements
[   7   8   9   1   2   3   4   5   6 ]
Element 9 exist in location 2
Element 3 exist in location 5

Array Elements
[   11   22   43   45   51   62   73   1   9   10 ]
Element 9 exist in location 8
Element 11 exist in location 0
Element 67 Are not exist``````

## Resultant Output Explanation

The given C program applies the binary search algorithm on two example arrays, `arr1` and `arr2`, and finds specific target elements. It then displays the results.

In the output, for `arr1`, the algorithm successfully finds elements 9 and 3 at indices 2 and 5, respectively. For `arr2`, the algorithm finds elements 9 and 11 at indices 8 and 0, respectively, while element 67 is not present in the array.

## Time Complexity

The time complexity of the binary search algorithm in the given code is O(log n) since it reduces the search space by half in each recursive call. The algorithm performs binary search recursively on the left or right half of the array based on the comparisons, making it efficient for sorted and rotated arrays.

In conclusion, the given algorithm effectively solves the problem of finding an element in a sorted and rotated array using a modified binary search approach. It has a time complexity of O(log n) and can efficiently handle arrays with repeated elements.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post