# Search an element in a sorted and rotated array

The problem involves searching for an element in a sorted and rotated array. This scenario occurs when an initially sorted array is rotated at some point, potentially disrupting its sorted order. Your objective is to find a specific target element within this sorted and rotated array efficiently.

## Problem Statement

Given a sorted and rotated array `arr` and a target value `value`, you need to determine whether the target value exists in the array. If it does, you also need to find its index.

## Example

Let's consider the sorted and rotated array `arr1 = [7, 8, 9, 1, 2, 3, 4, 5, 6]`. If we want to find the element `3`, the expected output should be "Element 3 at index: 5", indicating that the element `3` is present at index `5` in the array.

## Idea to Solve

To efficiently search for an element in a sorted and rotated array, we can modify the binary search algorithm. The key insight is to identify which part of the array is still sorted and then determine whether the target value might be present in that sorted portion. If it is, we perform a standard binary search in that part; otherwise, we search the other part recursively.

## Pseudocode

``````function search(arr, low, high, value):
if low > high:
return -1
mid = low + (high - low) / 2
if arr[mid] == value:
return mid
if arr[low] <= arr[mid]:
if value >= arr[low] && value <= arr[mid]:
return search(arr, low, mid - 1, value)
else:
return search(arr, mid + 1, high, value)
if value >= arr[mid] && value <= arr[high]:
return search(arr, mid + 1, high, value)
return search(arr, low, mid - 1, value)``````

## Algorithm Explanation

• The base case checks if `low` is greater than `high`, indicating an empty sub-array, and returns `-1` to indicate that the value was not found.
• The middle index `mid` is calculated to divide the current sub-array into two halves.
• We compare the element at `mid` with the target `value`.
• If they are equal, we return the index `mid`.
• If the left half (from `low` to `mid`) is sorted, we check whether the `value` falls within that sorted range. If it does, we recursively search in the left half; otherwise, we search in the right half.
• If the right half (from `mid` to `high`) is sorted and the `value` falls within that range, we recursively search in the right half; otherwise, we search in the left half.

## Code Solution

``````//  C program for
//  Search an element in a sorted and rotated array
#include <stdio.h>
//Display array elements
void display(int arr[], int n)
{
printf("\n\n Array Elements \n [");
for (int i = 0; i < n; ++i)
{
printf("   %d", arr[i]);
}
printf("  ]\n");
}
int search(int arr[], int low, int high, int value)
{
if (low > high)
{
return -1;
}
// Find middle element
int mid = low + ((high - low) / 2);
if (arr[mid] == value)
{
return mid;
}
else if (arr[low] <= arr[mid])
{
if (value >= arr[low] && value <= arr[mid])
{
return search(arr, low, mid - 1, value);
}
return search(arr, mid + 1, high, value);
}
if (value >= arr[mid] && value <= arr[high])
{
return search(arr, mid + 1, high, value);
}
return search(arr, low, mid - 1, value);
}
void findElement(int arr[], int n, int value)
{
int index = 0;
if (n > 1)
{
index = search(arr, 0, n - 1, value);
}
if (index != -1 && arr[index] == value)
{
printf(" Element %d at index : %d \n", value, index);
}
else
{
printf(" Element %d not exists\n", value);
}
}
int main(int argc, char
const *argv[])
{
// 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 , 2 , 9 , 10
};
int arr3[] = {
2 , 2 , 5 , -1 , 1 , 2
};
// Get the size
int size = sizeof(arr1) / sizeof(arr1[0]);
display(arr1, size);
// value = 3
findElement(arr1, size, 3);
// value = 8
findElement(arr1, size, 8);
// Get the size
size = sizeof(arr2) / sizeof(arr2[0]);
display(arr2, size);
// Test Case B
findElement(arr2, size, 73);
findElement(arr2, size, 45);
// Get the size
size = sizeof(arr3) / sizeof(arr3[0]);
display(arr3, size);
// Test Case C
findElement(arr3, size, 3);
return 0;
}``````

#### Output

`````` Array Elements
[   7   8   9   1   2   3   4   5   6  ]
Element 3 at index : 5
Element 8 at index : 1

Array Elements
[   11   22   43   45   51   62   73   2   9   10  ]
Element 73 at index : 6
Element 45 at index : 3

Array Elements
[   2   2   5   -1   1   2  ]
Element 3 not exists``````
``````// Java Program
// Search an element in a sorted and rotated array
public class Searching
{
//Display array elements
public void display(int[] arr, int n)
{
System.out.print("\n\n Array Elements \n [");
for (int i = 0; i < n; ++i)
{
System.out.print(" " + arr[i]);
}
System.out.print(" ]\n");
}
public int search(int[] arr, int low, int high, int value)
{
if (low > high)
{
return -1;
}
// Find middle element
int mid = low + ((high - low) / 2);
if (arr[mid] == value)
{
return mid;
}
else if (arr[low] <= arr[mid])
{
if (value >= arr[low] && value <= arr[mid])
{
return search(arr, low, mid - 1, value);
}
return search(arr, mid + 1, high, value);
}
if (value >= arr[mid] && value <= arr[high])
{
return search(arr, mid + 1, high, value);
}
return search(arr, low, mid - 1, value);
}
public void findElement(int[] arr, int n, int value)
{
int index = 0;
if (n > 1)
{
index = search(arr, 0, n - 1, value);
}
if (index != -1 && arr[index] == value)
{
System.out.println(" Element " + value + " at index : " + index);
}
else
{
System.out.print(" Element " + value + " not exists\n");
}
}
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 , 2 , 9 , 10
};
int[] arr3 = {
2 , 2 , 5 , -1 , 1 , 2
};
// Get the size
int size = arr1.length;
// value = 3
// value = 8
// Get the size
size = arr2.length;
// Test Case B
// Get the size
size = arr3.length;
// Test Case C
}
}``````

#### Output

`````` Array Elements
[ 7 8 9 1 2 3 4 5 6 ]
Element 3 at index : 5
Element 8 at index : 1

Array Elements
[ 11 22 43 45 51 62 73 2 9 10 ]
Element 73 at index : 6
Element 45 at index : 3

Array Elements
[ 2 2 5 -1 1 2 ]
Element 3 not exists``````
``````// Include header file
#include <iostream>
using namespace std;
// C++ Program
// Search an element in a sorted and rotated array
class Searching
{
public:
//Display array elements
void display(int arr[], int n)
{
cout << "\n\n Array Elements \n [";
for (int i = 0; i < n; ++i)
{
cout << " " << arr[i];
}
cout << " ]\n";
}
int search(int arr[], int low, int high, int value)
{
if (low > high)
{
return -1;
}
// Find middle element
int mid = low + ((high - low) / 2);
if (arr[mid] == value)
{
return mid;
}
else if (arr[low] <= arr[mid])
{
if (value >= arr[low] && value <= arr[mid])
{
return this->search(arr, low, mid - 1, value);
}
return this->search(arr, mid + 1, high, value);
}
if (value >= arr[mid] && value <= arr[high])
{
return this->search(arr, mid + 1, high, value);
}
return this->search(arr, low, mid - 1, value);
}
void findElement(int arr[], int n, int value)
{
int index = 0;
if (n > 1)
{
index = this->search(arr, 0, n - 1, value);
}
if (index != -1 && arr[index] == value)
{
cout << " Element " << value
<< " at index : " << index << endl;
}
else
{
cout << " Element "
<< value << " not exists\n";
}
}
};
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 , 2 , 9 , 10
};
int arr3[] = {
2 , 2 , 5 , -1 , 1 , 2
};
// Get the size
int size = sizeof(arr1) / sizeof(arr1[0]);
// value = 3
// value = 8
// Get the size
size = sizeof(arr2) / sizeof(arr2[0]);
// Test Case B
// Get the size
size = sizeof(arr3) / sizeof(arr3[0]);
// Test Case C
return 0;
}``````

#### Output

`````` Array Elements
[ 7 8 9 1 2 3 4 5 6 ]
Element 3 at index : 5
Element 8 at index : 1

Array Elements
[ 11 22 43 45 51 62 73 2 9 10 ]
Element 73 at index : 6
Element 45 at index : 3

Array Elements
[ 2 2 5 -1 1 2 ]
Element 3 not exists``````
``````// Include namespace system
using System;
// Csharp Program
// Search an element in a sorted and rotated array
public class Searching
{
//Display array elements
public void display(int[] arr, int n)
{
Console.Write("\n\n Array Elements \n [");
for (int i = 0; i < n; ++i)
{
Console.Write(" " + arr[i]);
}
Console.Write(" ]\n");
}
public int search(int[] arr, int low, int high, int value)
{
if (low > high)
{
return -1;
}
// Find middle element
int mid = low + ((high - low) / 2);
if (arr[mid] == value)
{
return mid;
}
else if (arr[low] <= arr[mid])
{
if (value >= arr[low] && value <= arr[mid])
{
return this.search(arr, low, mid - 1, value);
}
return this.search(arr, mid + 1, high, value);
}
if (value >= arr[mid] && value <= arr[high])
{
return this.search(arr, mid + 1, high, value);
}
return this.search(arr, low, mid - 1, value);
}
public void findElement(int[] arr, int n, int value)
{
int index = 0;
if (n > 1)
{
index = this.search(arr, 0, n - 1, value);
}
if (index != -1 && arr[index] == value)
{
Console.WriteLine(" Element " + value + " at index : " + index);
}
else
{
Console.Write(" Element " + value + " not exists\n");
}
}
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 , 2 , 9 , 10
};
int[] arr3 = {
2 , 2 , 5 , -1 , 1 , 2
};
// Get the size
int size = arr1.Length;
// value = 3
// value = 8
// Get the size
size = arr2.Length;
// Test Case B
// Get the size
size = arr3.Length;
// Test Case C
}
}``````

#### Output

`````` Array Elements
[ 7 8 9 1 2 3 4 5 6 ]
Element 3 at index : 5
Element 8 at index : 1

Array Elements
[ 11 22 43 45 51 62 73 2 9 10 ]
Element 73 at index : 6
Element 45 at index : 3

Array Elements
[ 2 2 5 -1 1 2 ]
Element 3 not exists``````
``````package main
import "fmt"
// Go Program
// Search an element in a sorted and rotated array
type Searching struct {}
func getSearching() * Searching {
var me *Searching = &Searching {}
return me
}
//Display array elements
func(this Searching) display(arr[] int, n int) {
fmt.Print("\n\n Array Elements \n [")
for i := 0 ; i < n ; i++ {
fmt.Print(" ", arr[i])
}
fmt.Print(" ]\n")
}
func(this Searching) search(arr[] int, low int, high int, value int) int {
if low > high {
return -1
}
// Find middle element
var mid int = low + ((high - low) / 2)
if arr[mid] == value {
return mid
} else if arr[low] <= arr[mid] {
if value >= arr[low] && value <= arr[mid] {
return this.search(arr, low, mid - 1, value)
}
return this.search(arr, mid + 1, high, value)
}
if value >= arr[mid] && value <= arr[high] {
return this.search(arr, mid + 1, high, value)
}
return this.search(arr, low, mid - 1, value)
}
func(this Searching) findElement(arr[] int, n int, value int) {
var index int = 0
if n > 1 {
index = this.search(arr, 0, n - 1, value)
}
if index != -1 && arr[index] == value {
fmt.Println(" Element ", value, " at index : ", index)
} else {
fmt.Print(" Element ", value, " not exists\n")
}
}
func main() {
var task * Searching = getSearching()
// Defining sorted and rotated array of integer element
var arr1 = [] int {
7,
8,
9,
1,
2,
3,
4,
5,
6,
}
var arr2 = [] int {
11,
22,
43,
45,
51,
62,
73,
2,
9,
10,
}
var arr3 = [] int {
2,
2,
5,
-1,
1,
2,
}
// Get the size
var size int = len(arr1)
// value = 3
// value = 8
// Get the size
size = len(arr2)
// Test Case B
// Get the size
size = len(arr3)
// Test Case C
}``````

#### Output

`````` Array Elements
[ 7 8 9 1 2 3 4 5 6 ]
Element 3 at index : 5
Element 8 at index : 1

Array Elements
[ 11 22 43 45 51 62 73 2 9 10 ]
Element 73 at index : 6
Element 45 at index : 3

Array Elements
[ 2 2 5 -1 1 2 ]
Element 3 not exists``````
``````<?php
// Php Program
// Search an element in a sorted and rotated array
class Searching
{
//Display array elements
public	function display(\$arr, \$n)
{
echo("\n\n Array Elements \n [");
for (\$i = 0; \$i < \$n; ++\$i)
{
echo(" ".\$arr[\$i]);
}
echo(" ]\n");
}
public	function search(\$arr, \$low, \$high, \$value)
{
if (\$low > \$high)
{
return -1;
}
// Find middle element
\$mid = \$low + ((int)((\$high - \$low) / 2));
if (\$arr[\$mid] == \$value)
{
return \$mid;
}
else if (\$arr[\$low] <= \$arr[\$mid])
{
if (\$value >= \$arr[\$low] && \$value <= \$arr[\$mid])
{
return \$this->search(\$arr, \$low, \$mid - 1, \$value);
}
return \$this->search(\$arr, \$mid + 1, \$high, \$value);
}
if (\$value >= \$arr[\$mid] && \$value <= \$arr[\$high])
{
return \$this->search(\$arr, \$mid + 1, \$high, \$value);
}
return \$this->search(\$arr, \$low, \$mid - 1, \$value);
}
public	function findElement(\$arr, \$n, \$value)
{
\$index = 0;
if (\$n > 1)
{
\$index = \$this->search(\$arr, 0, \$n - 1, \$value);
}
if (\$index != -1 && \$arr[\$index] == \$value)
{
echo(" Element ".\$value.
" at index : ".\$index.
"\n");
}
else
{
echo(" Element ".\$value.
" not exists\n");
}
}
}

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, 2, 9, 10);
\$arr3 = array(2, 2, 5, -1, 1, 2);
// Get the size
\$size = count(\$arr1);
// value = 3
// value = 8
// Get the size
\$size = count(\$arr2);
// Test Case B
// Get the size
\$size = count(\$arr3);
// Test Case C
}
main();``````

#### Output

`````` Array Elements
[ 7 8 9 1 2 3 4 5 6 ]
Element 3 at index : 5
Element 8 at index : 1

Array Elements
[ 11 22 43 45 51 62 73 2 9 10 ]
Element 73 at index : 6
Element 45 at index : 3

Array Elements
[ 2 2 5 -1 1 2 ]
Element 3 not exists``````
``````// Node JS Program
// Search an element in a sorted and rotated array
class Searching
{
//Display array elements
display(arr, n)
{
process.stdout.write("\n\n Array Elements \n [");
for (var i = 0; i < n; ++i)
{
process.stdout.write(" " + arr[i]);
}
process.stdout.write(" ]\n");
}
search(arr, low, high, value)
{
if (low > high)
{
return -1;
}
// Find middle element
var mid = low + (parseInt((high - low) / 2));
if (arr[mid] == value)
{
return mid;
}
else if (arr[low] <= arr[mid])
{
if (value >= arr[low] && value <= arr[mid])
{
return this.search(arr, low, mid - 1, value);
}
return this.search(arr, mid + 1, high, value);
}
if (value >= arr[mid] && value <= arr[high])
{
return this.search(arr, mid + 1, high, value);
}
return this.search(arr, low, mid - 1, value);
}
findElement(arr, n, value)
{
var index = 0;
if (n > 1)
{
index = this.search(arr, 0, n - 1, value);
}
if (index != -1 && arr[index] == value)
{
console.log(" Element " + value + " at index : " + index);
}
else
{
process.stdout.write(" Element " + value + " not exists\n");
}
}
}

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, 2, 9, 10];
var arr3 = [2, 2, 5, -1, 1, 2];
// Get the size
var size = arr1.length;
// value = 3
// value = 8
// Get the size
size = arr2.length;
// Test Case B
// Get the size
size = arr3.length;
// Test Case C
}
main();``````

#### Output

`````` Array Elements
[ 7 8 9 1 2 3 4 5 6 ]
Element 3 at index : 5
Element 8 at index : 1

Array Elements
[ 11 22 43 45 51 62 73 2 9 10 ]
Element 73 at index : 6
Element 45 at index : 3

Array Elements
[ 2 2 5 -1 1 2 ]
Element 3 not exists``````
``````#  Python 3 Program
#  Search an element in a sorted and rotated array
class Searching :
# Display list elements
def display(self, arr, n) :
print("\n\n Array Elements \n [", end = "")
i = 0
while (i < n) :
print(" ", arr[i], end = "")
i += 1

print(" ]")

def search(self, arr, low, high, value) :
if (low > high) :
return -1

#  Find middle element
mid = low + (int((high - low) / 2))
if (arr[mid] == value) :
return mid
elif (arr[low] <= arr[mid]) :
if (value >= arr[low] and value <= arr[mid]) :
return self.search(arr, low, mid - 1, value)

return self.search(arr, mid + 1, high, value)

if (value >= arr[mid] and value <= arr[high]) :
return self.search(arr, mid + 1, high, value)

return self.search(arr, low, mid - 1, value)

def findElement(self, arr, n, value) :
index = 0
if (n > 1) :
index = self.search(arr, 0, n - 1, value)

if (index != -1 and arr[index] == value) :
print(" Element ", value ," at index : ", index)
else :
print(" Element ", value ," not exists")

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

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

#### Output

`````` Array Elements
[  7  8  9  1  2  3  4  5  6 ]
Element  3  at index :  5
Element  8  at index :  1

Array Elements
[  11  22  43  45  51  62  73  2  9  10 ]
Element  73  at index :  6
Element  45  at index :  3

Array Elements
[  2  2  5  -1  1  2 ]
Element  3  not exists``````
``````#  Ruby Program
#  Search an element in a sorted and rotated array
class Searching
# Display array elements
def display(arr, n)
print("\n\n Array Elements \n [")
i = 0
while (i < n)
print(" ", arr[i])
i += 1
end

print(" ]\n")
end

def search(arr, low, high, value)
if (low > high)
return -1
end

#  Find middle element
mid = low + ((high - low) / 2)
if (arr[mid] == value)
return mid
elsif (arr[low] <= arr[mid])
if (value >= arr[low] && value <= arr[mid])
return self.search(arr, low, mid - 1, value)
end

return self.search(arr, mid + 1, high, value)
end

if (value >= arr[mid] && value <= arr[high])
return self.search(arr, mid + 1, high, value)
end

return self.search(arr, low, mid - 1, value)
end

def findElement(arr, n, value)
index = 0
if (n > 1)
index = self.search(arr, 0, n - 1, value)
end

if (index != -1 && arr[index] == value)
print(" Element ", value ," at index : ", index, "\n")
else

print(" Element ", value ," not exists\n")
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, 2, 9, 10]
arr3 = [2, 2, 5, -1, 1, 2]
#  Get the size
size = arr1.length
#  value = 3
#  value = 8
#  Get the size
size = arr2.length
#  Test Case B
#  Get the size
size = arr3.length
#  Test Case C
end

main()``````

#### Output

``````
Array Elements
[ 7 8 9 1 2 3 4 5 6 ]
Element 3 at index : 5
Element 8 at index : 1

Array Elements
[ 11 22 43 45 51 62 73 2 9 10 ]
Element 73 at index : 6
Element 45 at index : 3

Array Elements
[ 2 2 5 -1 1 2 ]
Element 3 not exists
``````
``````// Scala Program
// Search an element in a sorted and rotated array
class Searching()
{
//Display array elements
def display(arr: Array[Int], n: Int): Unit = {
print("\n\n Array Elements \n [");
var i: Int = 0;
while (i < n)
{
print(" " + arr(i));
i += 1;
}
print(" ]\n");
}
def search(arr: Array[Int], low: Int,
high: Int, value: Int): Int = {
if (low > high)
{
return -1;
}
// Find middle element
var mid: Int = low + ((high - low) / 2);
if (arr(mid) == value)
{
return mid;
}
else if (arr(low) <= arr(mid))
{
if (value >= arr(low) && value <= arr(mid))
{
return search(arr, low, mid - 1, value);
}
return search(arr, mid + 1, high, value);
}
if (value >= arr(mid) && value <= arr(high))
{
return search(arr, mid + 1, high, value);
}
return search(arr, low, mid - 1, value);
}
def findElement(arr: Array[Int], n: Int, value: Int): Unit = {
var index: Int = 0;
if (n > 1)
{
index = search(arr, 0, n - 1, value);
}
if (index != -1 && arr(index) == value)
{
println(" Element " + value + " at index : " + index);
}
else
{
print(" Element " + value + " not exists\n");
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Searching = new Searching();
// 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, 2, 9, 10);
var arr3: Array[Int] = Array(2, 2, 5, -1, 1, 2);
// Get the size
var size: Int = arr1.length;
// value = 3
// value = 8
// Get the size
size = arr2.length;
// Test Case B
// Get the size
size = arr3.length;
// Test Case C
}
}``````

#### Output

`````` Array Elements
[ 7 8 9 1 2 3 4 5 6 ]
Element 3 at index : 5
Element 8 at index : 1

Array Elements
[ 11 22 43 45 51 62 73 2 9 10 ]
Element 73 at index : 6
Element 45 at index : 3

Array Elements
[ 2 2 5 -1 1 2 ]
Element 3 not exists``````
``````import Foundation;
// Swift 4 Program
// Search an element in a sorted and rotated array
class Searching
{
//Display array elements
func display(_ arr: [Int], _ n: Int)
{
print("\n\n Array Elements \n [", terminator: "");
var i: Int = 0;
while (i < n)
{
print(" ", arr[i], terminator: "");
i += 1;
}
print(" ]");
}
func search(_ arr: [Int], _ low: Int,
_ high: Int, _ value: Int) -> Int
{
if (low > high)
{
return -1;
}
// Find middle element
let mid: Int = low + ((high - low) / 2);
if (arr[mid] == value)
{
return mid;
}
else if (arr[low] <= arr[mid])
{
if (value >= arr[low] && value <= arr[mid])
{
return self.search(arr, low, mid - 1, value);
}
return self.search(arr, mid + 1, high, value);
}
if (value >= arr[mid] && value <= arr[high])
{
return self.search(arr, mid + 1, high, value);
}
return self.search(arr, low, mid - 1, value);
}
func findElement(_ arr: [Int], _ n: Int, _ value: Int)
{
var index: Int = 0;
if (n > 1)
{
index = self.search(arr, 0, n - 1, value);
}
if (index  != -1 && arr[index] == value)
{
print(" Element ", value ," at index : ", index);
}
else
{
print(" Element ", value ," not exists");
}
}
}
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, 2, 9, 10];
let arr3: [Int] = [2, 2, 5, -1, 1, 2];
// Get the size
var size: Int = arr1.count;
// value = 3
// value = 8
// Get the size
size = arr2.count;
// Test Case B
// Get the size
size = arr3.count;
// Test Case C
}
main();``````

#### Output

`````` Array Elements
[  7  8  9  1  2  3  4  5  6 ]
Element  3  at index :  5
Element  8  at index :  1

Array Elements
[  11  22  43  45  51  62  73  2  9  10 ]
Element  73  at index :  6
Element  45  at index :  3

Array Elements
[  2  2  5  -1  1  2 ]
Element  3  not exists``````
``````// Kotlin Program
// Search an element in a sorted and rotated array
class Searching
{
//Display array elements
fun display(arr: Array < Int > , n: Int): Unit
{
print("\n\n Array Elements \n [");
var i: Int = 0;
while (i < n)
{
print(" " + arr[i]);
i += 1;
}
print(" ]\n");
}
fun search(arr: Array < Int > ,
low: Int, high: Int,
value: Int): Int
{
if (low > high)
{
return -1;
}
// Find middle element
val mid: Int = low + ((high - low) / 2);
if (arr[mid] == value)
{
return mid;
}
else if (arr[low] <= arr[mid])
{
if (value >= arr[low] && value <= arr[mid])
{
return this.search(arr, low, mid - 1, value);
}
return this.search(arr, mid + 1, high, value);
}
if (value >= arr[mid] && value <= arr[high])
{
return this.search(arr, mid + 1, high, value);
}
return this.search(arr, low, mid - 1, value);
}
fun findElement(arr: Array < Int > , n: Int, value: Int): Unit
{
var index: Int = 0;
if (n > 1)
{
index = this.search(arr, 0, n - 1, value);
}
if (index != -1 && arr[index] == value)
{
println(" Element " + value + " at index : " + index);
}
else
{
print(" Element " + value + " not exists\n");
}
}
}
fun main(args: Array < String > ): Unit
{
// Defining sorted and rotated array of integer element
val arr1: Array < Int > = arrayOf(7, 8, 9, 1, 2, 3, 4, 5, 6);
val arr2: Array < Int > = arrayOf(11, 22, 43, 45, 51, 62, 73, 2, 9, 10);
val arr3: Array < Int > = arrayOf(2, 2, 5, -1, 1, 2);
// Get the size
var size: Int = arr1.count();
// value = 3
// value = 8
// Get the size
size = arr2.count();
// Test Case B
// Get the size
size = arr3.count();
// Test Case C
}``````

#### Output

`````` Array Elements
[ 7 8 9 1 2 3 4 5 6 ]
Element 3 at index : 5
Element 8 at index : 1

Array Elements
[ 11 22 43 45 51 62 73 2 9 10 ]
Element 73 at index : 6
Element 45 at index : 3

Array Elements
[ 2 2 5 -1 1 2 ]
Element 3 not exists``````

## Time Complexity

The time complexity of this algorithm is determined by the number of recursive calls. In each call, the size of the search space is effectively halved. Thus, the algorithm has a time complexity of `O(log n)`, where `n` is the number of elements in the array.

## 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.