Skip to main content

Search for an element in a mountain array

In this article, we will discuss the problem of searching for an element in a mountain array. We will provide an explanation of the problem, present a pseudocode algorithm to solve it, and discuss the resulting output. Additionally, we will include the time complexity of the code.

The problem of searching for an element in a mountain array involves finding a specific element within an array that first increases and then decreases in value. The array is known as a mountain array due to its shape. This problem requires an efficient algorithm to locate the desired element in the array.

Problem Statement

Given a mountain array, the task is to search for a specific element within it. The array may contain positive or negative integers. If the element is found, the position of its first occurrence should be returned; otherwise, a message indicating that the element does not exist in the array should be displayed.

Pseudocode Algorithm

Below is the pseudocode algorithm to solve the problem: 

1. Function findElement(arr, i, j, x):
2.     if i > j:
3.         return -1 (Element not found)
4.     if arr[i] == x:
5.         return i (Element found at position i)
6.     if arr[j] == x:
7.         return j (Element found at position j)
8.     mid = i + ((i + j) / 2)
9.     if arr[mid] == x:
10.        return mid (Element found at position mid)
11.    if arr[mid] > x:
12.        mid = findElement(arr, i + 1, mid - 1, x) (Search in the left subarray)
13.        if mid != -1:
14.            return mid (Element found in the left subarray)
15.    mid = findElement(arr, mid + 1, j - 1, x) (Search in the right subarray)
16.    return mid (Element found in the right subarray)
17. 
18. Function search(arr, n, x):
19.    position = findElement(arr, 0, n - 1, x) (Call findElement to search for element x)
20.    if position == -1:
21.        print("Element does not exist in the array")
22.    else:
23.        print("Element exists at position", position)
24. 
25. Main:
26.    Initialize array arr
27.    n = length of arr
28.    Display array elements
29.    Call search(arr, n, x1) for testing different elements

Code Solution

// C Program
// Search for an element in a mountain array
#include <stdio.h>
 //Function which is display array elements
void display(int arr[], int n)
{
	for (int i = 0; i < n; ++i)
	{
		printf("%d ", arr[i]);
	}
}
int findElement(int arr[], int i, int j, int x)
{
	if (i > j)
	{
		// When element not found
		return -1;
	}
	if (arr[i] == x)
	{
		// When element x exists in i-th position
		return i;
	}
	if (arr[j] == x)
	{
		// When element x exists in j-th position
		return j;
	}
	if (i > j)
	{
		// When element not found
		return -1;
	}
	int mid = i + ((i + j) / 2);
	if (arr[mid] == x)
	{
		// When element x found in mid position
		return mid;
	}
	if (arr[mid] > x)
	{
		// left subarray test
		mid = findElement(arr, i + 1, mid - 1, x);
		if (mid != -1)
		{
			// When we get result
			return mid;
		}
	}
	// right subarray test
	mid = findElement(arr, mid + 1, j - 1, x);
	return mid;
}
void search(int arr[], int n, int x)
{
	printf("\n Given element : %d", x);
	int position = findElement(arr, 0, n - 1, x);
	if (position == -1)
	{
		printf("\n Element not exists ");
	}
	else
	{
		printf("\n Exists in %d position", position);
	}
}
int main()
{
	int arr[] = {
		-3 , 2 , 1 , 4 , 6 , 4 , 3 , 1 , -4 , -5
	};
	int n = sizeof(arr) / sizeof(arr[0]);
	// Display array element
	display(arr, n);
	// Test A
	// X = 3
	search(arr, n, 3);
	// Test B
	// X = 1
	search(arr, n, 1);
	// Test C
	// X = 5
	search(arr, n, 5);
	return 0;
}

Output

-3 2 1 4 6 4 3 1 -4 -5
 Given element : 3
 Exists in 6 position
 Given element : 1
 Exists in 2 position
 Given element : 5
 Element not exists
/*
    Java Program for
    Search for an element in a mountain array
*/
public class Searching
{
   //Function which is display array elements
    public void display(int[] arr, int n)
    {
        for (int i = 0; i < n; ++i)
        {
            System.out.print("  " + arr[i]);
        }
    }
    public int findElement(int[] arr, int i, int j, int x)
    {
        if (i > j)
        {
            // When element not found
            return -1;
        }
        if (arr[i] == x)
        {
            // When element x exists in i-th position
            return i;
        }
        if (arr[j] == x)
        {
            // When element x exists in j-th position
            return j;
        }
        if (i == j)
        {
            // When element not found
            return -1;
        }
        int mid = i + ((i + j) / 2);
        if (arr[mid] == x)
        {
            // When element x found in mid position
            return mid;
        }
        if (arr[mid] > x)
        {
            // left subarray test
            mid = findElement(arr, i + 1, mid - 1, x);
            if (mid != -1)
            {
                // When we get result
                return mid;
            }
        }
        // right subarray test
        mid = findElement(arr, mid + 1, j - 1, x);
        return mid;
    }
    // Handles the request of searching an element
    public void search(int[] arr, int n, int x)
    {
        System.out.print("\n Given element : " + x );

        int position = findElement(arr, 0, n - 1, x);

        if (position == -1)
        {
            // When element is not found
            System.out.print("\n Element not exists ");
        }
        else
        {
            System.out.print("\n Exists in " + position + " position");
        }
    }
    public static void main(String[] args)
    {
        Searching task = new Searching();

        // mounting array
        // First elements in increasing order then the decreasing order element
        int[] arr = {
            -3 , 2 , 1 , 4 , 6 , 4 , 3 , 1 , -4 , -5
        };
        int n = arr.length;
        // Display array element
        task.display(arr, n);
        // Test A
        // X = 3
        task.search(arr, n, 3);
        // Test B
        // X = 1
        task.search(arr, n, 1);
        // Test C
        // X = 5
        task.search(arr, n, 5);
    }
}

Output

  -3  2  1  4  6  4  3  1  -4  -5
 Given element : 3
 Exists in 6 position
 Given element : 1
 Exists in 2 position
 Given element : 5
 Element not exists
// Include header file
#include <iostream>
using namespace std;
/*
    C++ Program for
    Search for an element in a mountain array
*/
class Searching
{
	public:
		//Function which is display array elements
		void display(int arr[], int n)
		{
			for (int i = 0; i < n; ++i)
			{
				cout << "  " << arr[i];
			}
		}
	int findElement(int arr[], int i, int j, int x)
	{
		if (i > j)
		{
			// When element not found
			return -1;
		}
		if (arr[i] == x)
		{
			// When element x exists in i-th position
			return i;
		}
		if (arr[j] == x)
		{
			// When element x exists in j-th position
			return j;
		}
		if (i == j)
		{
			// When element not found
			return -1;
		}
		int mid = i + ((i + j) / 2);
		if (arr[mid] == x)
		{
			// When element x found in mid position
			return mid;
		}
		if (arr[mid] > x)
		{
			// left subarray test
			mid = this->findElement(arr, i + 1, mid - 1, x);
			if (mid != -1)
			{
				// When we get result
				return mid;
			}
		}
		// right subarray test
		mid = this->findElement(arr, mid + 1, j - 1, x);
		return mid;
	}
	// Handles the request of searching an element
	void search(int arr[], int n, int x)
	{
		cout << "\n Given element : " << x;
		int position = this->findElement(arr, 0, n - 1, x);
		if (position == -1)
		{
			// When element is not found
			cout << "\n Element not exists ";
		}
		else
		{
			cout << "\n Exists in " << position << " position";
		}
	}
};
int main()
{
	Searching *task = new Searching();
	// mounting array
	// First elements in increasing order then the decreasing order element
	int arr[] = {
		-3 , 2 , 1 , 4 , 6 , 4 , 3 , 1 , -4 , -5
	};
	int n = sizeof(arr) / sizeof(arr[0]);
	// Display array element
	task->display(arr, n);
	// Test A
	// X = 3
	task->search(arr, n, 3);
	// Test B
	// X = 1
	task->search(arr, n, 1);
	// Test C
	// X = 5
	task->search(arr, n, 5);
	return 0;
}

Output

  -3  2  1  4  6  4  3  1  -4  -5
 Given element : 3
 Exists in 6 position
 Given element : 1
 Exists in 2 position
 Given element : 5
 Element not exists
package main
import "fmt"
/*
    Go Program for
    Search for an element in a mountain array
*/
//Function which is display array elements
func display(arr[] int, n int) {
	for i := 0 ; i < n ; i++ {
		fmt.Print("  ", arr[i])
	}
}
func findElement(arr[] int, i int, j int, x int) int {
	if i > j {
		// When element not found
		return -1
	}
	if arr[i] == x {
		// When element x exists in i-th position
		return i
	}
	if arr[j] == x {
		// When element x exists in j-th position
		return j
	}
	if i == j {
		// When element not found
		return -1
	}
	var mid int = i + ((i + j) / 2)
	if arr[mid] == x {
		// When element x found in mid position
		return mid
	}
	if arr[mid] > x {
		// left subarray test
		mid = findElement(arr, i + 1, mid - 1, x)
		if mid != -1 {
			// When we get result
			return mid
		}
	}
	// right subarray test
	mid = findElement(arr, mid + 1, j - 1, x)
	return mid
}
// Handles the request of searching an element
func search(arr[] int, n int, x int) {
	fmt.Print("\n Given element : ", x)
	var position int = findElement(arr, 0, n - 1, x)
	if position == -1 {
		// When element is not found
		fmt.Print("\n Element not exists ")
	} else {
		fmt.Print("\n Exists in ", position, " position")
	}
}
func main() {
	
	// mounting array
	// First elements in increasing order then the decreasing order element
	var arr = [] int { -3, 2, 1, 4, 6, 4, 3, 1, -4, -5 }
	var n int = len(arr)
	// Display array element
	display(arr, n)
	// Test A
	// X = 3
	search(arr, n, 3)
	// Test B
	// X = 1
	search(arr, n, 1)
	// Test C
	// X = 5
	search(arr, n, 5)
}

Output

  -3  2  1  4  6  4  3  1  -4  -5
 Given element : 3
 Exists in 6 position
 Given element : 1
 Exists in 2 position
 Given element : 5
 Element not exists
// Include namespace system
using System;
/*
    Csharp Program for
    Search for an element in a mountain array
*/
public class Searching
{
	//Function which is display array elements
	public void display(int[] arr, int n)
	{
		for (int i = 0; i < n; ++i)
		{
			Console.Write("  " + arr[i]);
		}
	}
	public int findElement(int[] arr, int i, int j, int x)
	{
		if (i > j)
		{
			// When element not found
			return -1;
		}
		if (arr[i] == x)
		{
			// When element x exists in i-th position
			return i;
		}
		if (arr[j] == x)
		{
			// When element x exists in j-th position
			return j;
		}
		if (i == j)
		{
			// When element not found
			return -1;
		}
		int mid = i + ((i + j) / 2);
		if (arr[mid] == x)
		{
			// When element x found in mid position
			return mid;
		}
		if (arr[mid] > x)
		{
			// left subarray test
			mid = this.findElement(arr, i + 1, mid - 1, x);
			if (mid != -1)
			{
				// When we get result
				return mid;
			}
		}
		// right subarray test
		mid = this.findElement(arr, mid + 1, j - 1, x);
		return mid;
	}
	// Handles the request of searching an element
	public void search(int[] arr, int n, int x)
	{
		Console.Write("\n Given element : " + x);
		int position = this.findElement(arr, 0, n - 1, x);
		if (position == -1)
		{
			// When element is not found
			Console.Write("\n Element not exists ");
		}
		else
		{
			Console.Write("\n Exists in " + position + " position");
		}
	}
	public static void Main(String[] args)
	{
		Searching task = new Searching();
		// mounting array
		// First elements in increasing order then the decreasing order element
		int[] arr = {
			-3 , 2 , 1 , 4 , 6 , 4 , 3 , 1 , -4 , -5
		};
		int n = arr.Length;
		// Display array element
		task.display(arr, n);
		// Test A
		// X = 3
		task.search(arr, n, 3);
		// Test B
		// X = 1
		task.search(arr, n, 1);
		// Test C
		// X = 5
		task.search(arr, n, 5);
	}
}

Output

  -3  2  1  4  6  4  3  1  -4  -5
 Given element : 3
 Exists in 6 position
 Given element : 1
 Exists in 2 position
 Given element : 5
 Element not exists
<?php
/*
    Php Program for
    Search for an element in a mountain array
*/
class Searching
{
	//Function which is display array elements
	public function display($arr, $n)
	{
		for ($i = 0; $i < $n; ++$i)
		{
			echo("  ".$arr[$i]);
		}
	}
	public function findElement($arr, $i, $j, $x)
	{
		if ($i > $j)
		{
			// When element not found
			return -1;
		}
		if ($arr[$i] == $x)
		{
			// When element x exists in i-th position
			return $i;
		}
		if ($arr[$j] == $x)
		{
			// When element x exists in j-th position
			return $j;
		}
		if ($i == $j)
		{
			// When element not found
			return -1;
		}
		$mid = $i + ((int)(($i + $j) / 2));
		if ($arr[$mid] == $x)
		{
			// When element x found in mid position
			return $mid;
		}
		if ($arr[$mid] > $x)
		{
			// left subarray test
			$mid = $this->findElement($arr, $i + 1, $mid - 1, $x);
			if ($mid != -1)
			{
				// When we get result
				return $mid;
			}
		}
		// right subarray test
		$mid = $this->findElement($arr, $mid + 1, $j - 1, $x);
		return $mid;
	}
	// Handles the request of searching an element
	public function search($arr, $n, $x)
	{
		echo("\n Given element : ".$x);
		$position = $this->findElement($arr, 0, $n - 1, $x);
		if ($position == -1)
		{
			// When element is not found
			echo("\n Element not exists ");
		}
		else
		{
			echo("\n Exists in ".$position.
				" position");
		}
	}
}

function main()
{
	$task = new Searching();
	// mounting array
	// First elements in increasing order then the decreasing order element
	$arr = array(-3, 2, 1, 4, 6, 4, 3, 1, -4, -5);
	$n = count($arr);
	// Display array element
	$task->display($arr, $n);
	// Test A
	// X = 3
	$task->search($arr, $n, 3);
	// Test B
	// X = 1
	$task->search($arr, $n, 1);
	// Test C
	// X = 5
	$task->search($arr, $n, 5);
}
main();

Output

  -3  2  1  4  6  4  3  1  -4  -5
 Given element : 3
 Exists in 6 position
 Given element : 1
 Exists in 2 position
 Given element : 5
 Element not exists
/*
    Node JS Program for
    Search for an element in a mountain array
*/
class Searching
{
	//Function which is display array elements
	display(arr, n)
	{
		for (var i = 0; i < n; ++i)
		{
			process.stdout.write("  " + arr[i]);
		}
	}
	findElement(arr, i, j, x)
	{
		if (i > j)
		{
			// When element not found
			return -1;
		}
		if (arr[i] == x)
		{
			// When element x exists in i-th position
			return i;
		}
		if (arr[j] == x)
		{
			// When element x exists in j-th position
			return j;
		}
		if (i == j)
		{
			// When element not found
			return -1;
		}
		var mid = i + (parseInt((i + j) / 2));
		if (arr[mid] == x)
		{
			// When element x found in mid position
			return mid;
		}
		if (arr[mid] > x)
		{
			// left subarray test
			mid = this.findElement(arr, i + 1, mid - 1, x);
			if (mid != -1)
			{
				// When we get result
				return mid;
			}
		}
		// right subarray test
		mid = this.findElement(arr, mid + 1, j - 1, x);
		return mid;
	}
	// Handles the request of searching an element
	search(arr, n, x)
	{
		process.stdout.write("\n Given element : " + x);
		var position = this.findElement(arr, 0, n - 1, x);
		if (position == -1)
		{
			// When element is not found
			process.stdout.write("\n Element not exists ");
		}
		else
		{
			process.stdout.write("\n Exists in " + position + " position");
		}
	}
}

function main()
{
	var task = new Searching();
	// mounting array
	// First elements in increasing order then the decreasing order element
	var arr = [-3, 2, 1, 4, 6, 4, 3, 1, -4, -5];
	var n = arr.length;
	// Display array element
	task.display(arr, n);
	// Test A
	// X = 3
	task.search(arr, n, 3);
	// Test B
	// X = 1
	task.search(arr, n, 1);
	// Test C
	// X = 5
	task.search(arr, n, 5);
}
main();

Output

  -3  2  1  4  6  4  3  1  -4  -5
 Given element : 3
 Exists in 6 position
 Given element : 1
 Exists in 2 position
 Given element : 5
 Element not exists
#    Python 3 Program for
#    Search for an element in a mountain array
class Searching :
	# Function which is display list elements
	def display(self, arr, n) :
		i = 0
		while (i < n) :
			print("  ", arr[i], end = "")
			i += 1
		
	
	def findElement(self, arr, i, j, x) :
		if (i > j) :
			#  When element not found
			return -1
		
		if (arr[i] == x) :
			#  When element x exists in i-th position
			return i
		
		if (arr[j] == x) :
			#  When element x exists in j-th position
			return j
		
		if (i == j) :
			#  When element not found
			return -1
		
		mid = i + (int((i + j) / 2))
		if (arr[mid] == x) :
			#  When element x found in mid position
			return mid
		
		if (arr[mid] > x) :
			#  left sublist test
			mid = self.findElement(arr, i + 1, mid - 1, x)
			if (mid != -1) :
				#  When we get result
				return mid
			
		
		#  right sublist test
		mid = self.findElement(arr, mid + 1, j - 1, x)
		return mid
	
	#  Handles the request of searching an element
	def search(self, arr, n, x) :
		print("\n Given element : ", x, end = "")
		position = self.findElement(arr, 0, n - 1, x)
		if (position == -1) :
			#  When element is not found
			print("\n Element not exists ", end = "")
		else :
			print("\n Exists in ", position ," position", end = "")
		
	

def main() :
	task = Searching()
	#  mounting list
	#  First elements in increasing order then the decreasing order element
	arr = [-3, 2, 1, 4, 6, 4, 3, 1, -4, -5]
	n = len(arr)
	#  Display list element
	task.display(arr, n)
	#  Test A
	#  X = 3
	task.search(arr, n, 3)
	#  Test B
	#  X = 1
	task.search(arr, n, 1)
	#  Test C
	#  X = 5
	task.search(arr, n, 5)

if __name__ == "__main__": main()

Output

   -3   2   1   4   6   4   3   1   -4   -5
 Given element :  3
 Exists in  6  position
 Given element :  1
 Exists in  2  position
 Given element :  5
 Element not exists
#    Ruby Program for
#    Search for an element in a mountain array
class Searching 
	# Function which is display array elements
	def display(arr, n) 
		i = 0
		while (i < n) 
			print("  ", arr[i])
			i += 1
		end

	end

	def findElement(arr, i, j, x) 
		if (i > j) 
			#  When element not found
			return -1
		end

		if (arr[i] == x) 
			#  When element x exists in i-th position
			return i
		end

		if (arr[j] == x) 
			#  When element x exists in j-th position
			return j
		end

		if (i == j) 
			#  When element not found
			return -1
		end

		mid = i + ((i + j) / 2)
		if (arr[mid] == x) 
			#  When element x found in mid position
			return mid
		end

		if (arr[mid] > x) 
			#  left subarray test
			mid = self.findElement(arr, i + 1, mid - 1, x)
			if (mid != -1) 
				#  When we get result
				return mid
			end

		end

		#  right subarray test
		mid = self.findElement(arr, mid + 1, j - 1, x)
		return mid
	end

	#  Handles the request of searching an element
	def search(arr, n, x) 
		print("\n Given element : ", x)
		position = self.findElement(arr, 0, n - 1, x)
		if (position == -1) 
			#  When element is not found
			print("\n Element not exists ")
		else
 
			print("\n Exists in ", position ," position")
		end

	end

end

def main() 
	task = Searching.new()
	#  mounting array
	#  First elements in increasing order then the decreasing order element
	arr = [-3, 2, 1, 4, 6, 4, 3, 1, -4, -5]
	n = arr.length
	#  Display array element
	task.display(arr, n)
	#  Test A
	#  X = 3
	task.search(arr, n, 3)
	#  Test B
	#  X = 1
	task.search(arr, n, 1)
	#  Test C
	#  X = 5
	task.search(arr, n, 5)
end

main()

Output

  -3  2  1  4  6  4  3  1  -4  -5
 Given element : 3
 Exists in 6 position
 Given element : 1
 Exists in 2 position
 Given element : 5
 Element not exists 
/*
    Scala Program for
    Search for an element in a mountain array
*/
class Searching()
{
	//Function which is display array elements
	def display(arr: Array[Int], n: Int): Unit = {
		var i: Int = 0;
		while (i < n)
		{
			print("  " + arr(i));
			i += 1;
		}
	}
	def findElement(arr: Array[Int], i: Int, j: Int, x: Int): Int = {
		if (i > j)
		{
			// When element not found
			return -1;
		}
		if (arr(i) == x)
		{
			// When element x exists in i-th position
			return i;
		}
		if (arr(j) == x)
		{
			// When element x exists in j-th position
			return j;
		}
		if (i == j)
		{
			// When element not found
			return -1;
		}
		var mid: Int = i + ((i + j) / 2);
		if (arr(mid) == x)
		{
			// When element x found in mid position
			return mid;
		}
		if (arr(mid) > x)
		{
			// left subarray test
			mid = findElement(arr, i + 1, mid - 1, x);
			if (mid != -1)
			{
				// When we get result
				return mid;
			}
		}
		// right subarray test
		mid = findElement(arr, mid + 1, j - 1, x);
		return mid;
	}
	// Handles the request of searching an element
	def search(arr: Array[Int], n: Int, x: Int): Unit = {
		print("\n Given element : " + x);
		var position: Int = findElement(arr, 0, n - 1, x);
		if (position == -1)
		{
			// When element is not found
			print("\n Element not exists ");
		}
		else
		{
			print("\n Exists in " + position + " position");
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Searching = new Searching();
		// mounting array
		// First elements in increasing order then the decreasing order element
		var arr: Array[Int] = Array(-3, 2, 1, 4, 6, 4, 3, 1, -4, -5);
		var n: Int = arr.length;
		// Display array element
		task.display(arr, n);
		// Test A
		// X = 3
		task.search(arr, n, 3);
		// Test B
		// X = 1
		task.search(arr, n, 1);
		// Test C
		// X = 5
		task.search(arr, n, 5);
	}
}

Output

  -3  2  1  4  6  4  3  1  -4  -5
 Given element : 3
 Exists in 6 position
 Given element : 1
 Exists in 2 position
 Given element : 5
 Element not exists
import Foundation;
/*
    Swift 4 Program for
    Search for an element in a mountain array
*/
class Searching
{
	//Function which is display array elements
	func display(_ arr: [Int], _ n: Int)
	{
		var i: Int = 0;
		while (i < n)
		{
			print("  ", arr[i], terminator: "");
			i += 1;
		}
	}
	func findElement(_ arr: [Int], _ i: Int, _ j: Int, _ x: Int) -> Int
	{
		if (i > j)
		{
			// When element not found
			return -1;
		}
		if (arr[i] == x)
		{
			// When element x exists in i-th position
			return i;
		}
		if (arr[j] == x)
		{
			// When element x exists in j-th position
			return j;
		}
		if (i == j)
		{
			// When element not found
			return -1;
		}
		var mid: Int = i + ((i + j) / 2);
		if (arr[mid] == x)
		{
			// When element x found in mid position
			return mid;
		}
		if (arr[mid] > x)
		{
			// left subarray test
			mid = self.findElement(arr, i + 1, mid - 1, x);
			if (mid  != -1)
			{
				// When we get result
				return mid;
			}
		}
		// right subarray test
		mid = self.findElement(arr, mid + 1, j - 1, x);
		return mid;
	}
	// Handles the request of searching an element
	func search(_ arr: [Int], _ n: Int, _ x: Int)
	{
		print("\n Given element : ", x, terminator: "");
		let position: Int = self.findElement(arr, 0, n - 1, x);
		if (position == -1)
		{
			// When element is not found
			print("\n Element not exists ", terminator: "");
		}
		else
		{
			print("\n Exists in ", position ," position", terminator: "");
		}
	}
}
func main()
{
	let task: Searching = Searching();
	// mounting array
	// First elements in increasing order then the decreasing order element
	let arr: [Int] = [-3, 2, 1, 4, 6, 4, 3, 1, -4, -5];
	let n: Int = arr.count;
	// Display array element
	task.display(arr, n);
	// Test A
	// X = 3
	task.search(arr, n, 3);
	// Test B
	// X = 1
	task.search(arr, n, 1);
	// Test C
	// X = 5
	task.search(arr, n, 5);
}
main();

Output

   -3   2   1   4   6   4   3   1   -4   -5
 Given element :  3
 Exists in  6  position
 Given element :  1
 Exists in  2  position
 Given element :  5
 Element not exists
/*
    Kotlin Program for
    Search for an element in a mountain array
*/
class Searching
{
	//Function which is display array elements
	fun display(arr: Array < Int > , n: Int): Unit
	{
		var i: Int = 0;
		while (i < n)
		{
			print("  " + arr[i]);
			i += 1;
		}
	}
	fun findElement(arr: Array < Int > , i: Int, j: Int, x: Int): Int
	{
		if (i > j)
		{
			// When element not found
			return -1;
		}
		if (arr[i] == x)
		{
			// When element x exists in i-th position
			return i;
		}
		if (arr[j] == x)
		{
			// When element x exists in j-th position
			return j;
		}
		if (i == j)
		{
			// When element not found
			return -1;
		}
		var mid: Int = i + ((i + j) / 2);
		if (arr[mid] == x)
		{
			// When element x found in mid position
			return mid;
		}
		if (arr[mid] > x)
		{
			// left subarray test
			mid = this.findElement(arr, i + 1, mid - 1, x);
			if (mid != -1)
			{
				// When we get result
				return mid;
			}
		}
		// right subarray test
		mid = this.findElement(arr, mid + 1, j - 1, x);
		return mid;
	}
	// Handles the request of searching an element
	fun search(arr: Array < Int > , n: Int, x: Int): Unit
	{
		print("\n Given element : " + x);
		val position: Int = this.findElement(arr, 0, n - 1, x);
		if (position == -1)
		{
			// When element is not found
			print("\n Element not exists ");
		}
		else
		{
			print("\n Exists in " + position + " position");
		}
	}
}
fun main(args: Array < String > ): Unit
{
	val task: Searching = Searching();
	// mounting array
	// First elements in increasing order then the decreasing order element
	val arr: Array < Int > = arrayOf(-3, 2, 1, 4, 6, 4, 3, 1, -4, -5);
	val n: Int = arr.count();
	// Display array element
	task.display(arr, n);
	// Test A
	// X = 3
	task.search(arr, n, 3);
	// Test B
	// X = 1
	task.search(arr, n, 1);
	// Test C
	// X = 5
	task.search(arr, n, 5);
}

Output

  -3  2  1  4  6  4  3  1  -4  -5
 Given element : 3
 Exists in 6 position
 Given element : 1
 Exists in 2 position
 Given element : 5
 Element not exists

Explanation and Resultant Output

The given code starts by defining a display function that prints the elements of an array. Then, there's a findElement function that recursively searches for the desired element in the mountain array using a divide and conquer approach. It checks for various conditions and eventually returns the position of the element if found or -1 if not found. The search function calls findElement and displays the appropriate output based on the returned position. Finally, the main function initializes an array, determines its length, displays the array elements, and tests the search function with different elements.

The output of the code is as follows: 

-3 2 1 4 6 4 3 1 -4 -5
	Given element : 3
	Exists in 6 position
	Given element : 1
	Exists in 2 position
	Given element : 5
	Element not exists

The displayed output confirms that the code is correctly searching for elements in the mountain array. In the given tests, the element 3 is found at position 6, the element 1 is found at position 2, and the element 5 does not exist in the array.

Time Complexity

The time complexity of the provided code can be analyzed as follows:

  • The findElement function uses a binary search approach, which has a time complexity of O(log n), where n is the size of the array segment being searched.
  • The search function calls findElement once, resulting in a total time complexity of O(log n) for each search operation.
  • The overall time complexity of the code depends on the number of search operations performed.

In conclusion, the provided code efficiently searches for elements in a mountain array using a binary search approach. It displays the output based on whether the element is found or not found. The time complexity of the code is O(log n) for each search operation, where n is the size of the array segment being searched.

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