Search an element in a sorted and rotated array

Here given code implementation process.

//  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[])
	{
		Searching task = new Searching();
		// 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;
		task.display(arr1, size);
		// value = 3
		task.findElement(arr1, size, 3);
		// value = 8
		task.findElement(arr1, size, 8);
		// Get the size
		size = arr2.length;
		task.display(arr2, size);
		// Test Case B 
		task.findElement(arr2, size, 73);
		task.findElement(arr2, size, 45);
		// Get the size
		size = arr3.length;
		task.display(arr3, size);
		// Test Case C 
		task.findElement(arr3, size, 3);
	}
}

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()
{
	Searching *task = new Searching();
	// 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]);
	task->display(arr1, size);
	// value = 3
	task->findElement(arr1, size, 3);
	// value = 8
	task->findElement(arr1, size, 8);
	// Get the size
	size = sizeof(arr2) / sizeof(arr2[0]);
	task->display(arr2, size);
	// Test Case B 
	task->findElement(arr2, size, 73);
	task->findElement(arr2, size, 45);
	// Get the size
	size = sizeof(arr3) / sizeof(arr3[0]);
	task->display(arr3, size);
	// Test Case C 
	task->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
// 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)
	{
		Searching task = new Searching();
		// 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;
		task.display(arr1, size);
		// value = 3
		task.findElement(arr1, size, 3);
		// value = 8
		task.findElement(arr1, size, 8);
		// Get the size
		size = arr2.Length;
		task.display(arr2, size);
		// Test Case B 
		task.findElement(arr2, size, 73);
		task.findElement(arr2, size, 45);
		// Get the size
		size = arr3.Length;
		task.display(arr3, size);
		// Test Case C 
		task.findElement(arr3, size, 3);
	}
}

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)
	task.display(arr1, size)
	// value = 3
	task.findElement(arr1, size, 3)
	// value = 8
	task.findElement(arr1, size, 8)
	// Get the size
	size = len(arr2)
	task.display(arr2, size)
	// Test Case B 
	task.findElement(arr2, size, 73)
	task.findElement(arr2, size, 45)
	// Get the size
	size = len(arr3)
	task.display(arr3, size)
	// Test Case C 
	task.findElement(arr3, size, 3)
}

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()
{
	$task = new Searching();
	// 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);
	$task->display($arr1, $size);
	// value = 3
	$task->findElement($arr1, $size, 3);
	// value = 8
	$task->findElement($arr1, $size, 8);
	// Get the size
	$size = count($arr2);
	$task->display($arr2, $size);
	// Test Case B 
	$task->findElement($arr2, $size, 73);
	$task->findElement($arr2, $size, 45);
	// Get the size
	$size = count($arr3);
	$task->display($arr3, $size);
	// Test Case C 
	$task->findElement($arr3, $size, 3);
}
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()
{
	var task = new Searching();
	// 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;
	task.display(arr1, size);
	// value = 3
	task.findElement(arr1, size, 3);
	// value = 8
	task.findElement(arr1, size, 8);
	// Get the size
	size = arr2.length;
	task.display(arr2, size);
	// Test Case B 
	task.findElement(arr2, size, 73);
	task.findElement(arr2, size, 45);
	// Get the size
	size = arr3.length;
	task.display(arr3, size);
	// Test Case C 
	task.findElement(arr3, size, 3);
}
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() :
	task = Searching()
	#  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)
	task.display(arr1, size)
	#  value = 3
	task.findElement(arr1, size, 3)
	#  value = 8
	task.findElement(arr1, size, 8)
	#  Get the size
	size = len(arr2)
	task.display(arr2, size)
	#  Test Case B 
	task.findElement(arr2, size, 73)
	task.findElement(arr2, size, 45)
	#  Get the size
	size = len(arr3)
	task.display(arr3, size)
	#  Test Case C 
	task.findElement(arr3, size, 3)

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() 
	task = Searching.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, 2, 9, 10]
	arr3 = [2, 2, 5, -1, 1, 2]
	#  Get the size
	size = arr1.length
	task.display(arr1, size)
	#  value = 3
	task.findElement(arr1, size, 3)
	#  value = 8
	task.findElement(arr1, size, 8)
	#  Get the size
	size = arr2.length
	task.display(arr2, size)
	#  Test Case B 
	task.findElement(arr2, size, 73)
	task.findElement(arr2, size, 45)
	#  Get the size
	size = arr3.length
	task.display(arr3, size)
	#  Test Case C 
	task.findElement(arr3, size, 3)
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;
		task.display(arr1, size);
		// value = 3
		task.findElement(arr1, size, 3);
		// value = 8
		task.findElement(arr1, size, 8);
		// Get the size
		size = arr2.length;
		task.display(arr2, size);
		// Test Case B 
		task.findElement(arr2, size, 73);
		task.findElement(arr2, size, 45);
		// Get the size
		size = arr3.length;
		task.display(arr3, size);
		// Test Case C 
		task.findElement(arr3, size, 3);
	}
}

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()
{
	let task: Searching = Searching();
	// 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;
	task.display(arr1, size);
	// value = 3
	task.findElement(arr1, size, 3);
	// value = 8
	task.findElement(arr1, size, 8);
	// Get the size
	size = arr2.count;
	task.display(arr2, size);
	// Test Case B 
	task.findElement(arr2, size, 73);
	task.findElement(arr2, size, 45);
	// Get the size
	size = arr3.count;
	task.display(arr3, size);
	// Test Case C 
	task.findElement(arr3, size, 3);
}
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
{
	val task: Searching = Searching();
	// 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();
	task.display(arr1, size);
	// value = 3
	task.findElement(arr1, size, 3);
	// value = 8
	task.findElement(arr1, size, 8);
	// Get the size
	size = arr2.count();
	task.display(arr2, size);
	// Test Case B 
	task.findElement(arr2, size, 73);
	task.findElement(arr2, size, 45);
	// Get the size
	size = arr3.count();
	task.display(arr3, size);
	// Test Case C 
	task.findElement(arr3, size, 3);
}

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


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







© 2021, kalkicode.com, All rights reserved