Find an element in a sorted and rotated array
Finding an element in a sorted and rotated array using recursion refers to the process of searching for a specific element within an array that has been rotated (shifted) from its original sorted order.
In a sorted and rotated array, elements that were originally in ascending or descending order have been shifted such that they no longer appear in that order. For example, an array [7 , 8 , 9 , 1 , 2 , 3 , 4 , 5 , 6] has been rotated to the right by 3 positions. The element "9" that used to appear at index 2.
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[0]);
display(arr1, size);
findElement(arr1, size, 9);
findElement(arr1, size, 3);
// Get the size
size = sizeof(arr2) / sizeof(arr2[0]);
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)
{
SearchElement task = new SearchElement();
// 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;
task.display(arr1, size);
// Test Cases
task.findElement(arr1, size, 9);
task.findElement(arr1, size, 3);
// Get the size
size = arr2.length;
task.display(arr2, size);
// Test Cases
task.findElement(arr2, size, 9);
task.findElement(arr2, size, 11);
task.findElement(arr2, size, 67);
}
}
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()
{
SearchElement task = SearchElement();
// 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[0]);
task.display(arr1, size);
// Test Cases
task.findElement(arr1, size, 9);
task.findElement(arr1, size, 3);
// Get the size
size = sizeof(arr2) / sizeof(arr2[0]);
task.display(arr2, size);
// Test Cases
task.findElement(arr2, size, 9);
task.findElement(arr2, size, 11);
task.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
// 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)
{
SearchElement task = new SearchElement();
// 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;
task.display(arr1, size);
// Test Cases
task.findElement(arr1, size, 9);
task.findElement(arr1, size, 3);
// Get the size
size = arr2.Length;
task.display(arr2, size);
// Test Cases
task.findElement(arr2, size, 9);
task.findElement(arr2, size, 11);
task.findElement(arr2, size, 67);
}
}
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()
{
$task = new SearchElement();
// 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);
$task->display($arr1, $size);
// Test Cases
$task->findElement($arr1, $size, 9);
$task->findElement($arr1, $size, 3);
// Get the size
$size = count($arr2);
$task->display($arr2, $size);
// Test Cases
$task->findElement($arr2, $size, 9);
$task->findElement($arr2, $size, 11);
$task->findElement($arr2, $size, 67);
}
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()
{
var task = new SearchElement();
// 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;
task.display(arr1, size);
// Test Cases
task.findElement(arr1, size, 9);
task.findElement(arr1, size, 3);
// Get the size
size = arr2.length;
task.display(arr2, size);
// Test Cases
task.findElement(arr2, size, 9);
task.findElement(arr2, size, 11);
task.findElement(arr2, size, 67);
}
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() :
task = SearchElement()
# 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)
task.display(arr1, size)
# Test Cases
task.findElement(arr1, size, 9)
task.findElement(arr1, size, 3)
# Get the size
size = len(arr2)
task.display(arr2, size)
# Test Cases
task.findElement(arr2, size, 9)
task.findElement(arr2, size, 11)
task.findElement(arr2, size, 67)
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()
task = SearchElement.new()
# 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
task.display(arr1, size)
# Test Cases
task.findElement(arr1, size, 9)
task.findElement(arr1, size, 3)
# Get the size
size = arr2.length
task.display(arr2, size)
# Test Cases
task.findElement(arr2, size, 9)
task.findElement(arr2, size, 11)
task.findElement(arr2, size, 67)
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;
task.display(arr1, size);
// Test Cases
task.findElement(arr1, size, 9);
task.findElement(arr1, size, 3);
// Get the size
size = arr2.length;
task.display(arr2, size);
// Test Cases
task.findElement(arr2, size, 9);
task.findElement(arr2, size, 11);
task.findElement(arr2, size, 67);
}
}
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()
{
let task: SearchElement = SearchElement();
// 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;
task.display(arr1, size);
// Test Cases
task.findElement(arr1, size, 9);
task.findElement(arr1, size, 3);
// Get the size
size = arr2.count;
task.display(arr2, size);
// Test Cases
task.findElement(arr2, size, 9);
task.findElement(arr2, size, 11);
task.findElement(arr2, size, 67);
}
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
{
var task: SearchElement = SearchElement();
// 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();
task.display(arr1, size);
// Test Cases
task.findElement(arr1, size, 9);
task.findElement(arr1, size, 3);
// Get the size
size = arr2.count();
task.display(arr2, size);
// Test Cases
task.findElement(arr2, size, 9);
task.findElement(arr2, size, 11);
task.findElement(arr2, size, 67);
}
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
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.
New Comment