Skip to main content

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
Last updated on by Kalkicode




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.

New Comment