Posted on by Kalkicode
Code Divide And Conquer

# 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)
{
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)
{
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)
{
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)
{
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)
{
System.out.print("\n Element not exists ");
}
else
{
System.out.print("\n Exists in " + position + " position");
}
}
public static void main(String[] args)
{

// 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
// Test A
// X = 3
// Test B
// X = 1
// Test C
// X = 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)
{
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)
{
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)
{
cout << "\n Element not exists ";
}
else
{
cout << "\n Exists in " << position << " position";
}
}
};
int main()
{
// 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
// Test A
// X = 3
// Test B
// X = 1
// Test C
// X = 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 {
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 {
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 {
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)
{
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)
{
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)
{
Console.Write("\n Element not exists ");
}
else
{
Console.Write("\n Exists in " + position + " position");
}
}
public static void Main(String[] args)
{
// 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
// Test A
// X = 3
// Test B
// X = 1
// Test C
// X = 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)
{
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)
{
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)
{
echo("\n Element not exists ");
}
else
{
echo("\n Exists in ".\$position.
" position");
}
}
}

function main()
{
// 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
// Test A
// X = 3
// Test B
// X = 1
// Test C
// X = 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)
{
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)
{
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)
{
process.stdout.write("\n Element not exists ");
}
else
{
process.stdout.write("\n Exists in " + position + " position");
}
}
}

function main()
{
// 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
// Test A
// X = 3
// Test B
// X = 1
// Test C
// X = 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) :
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) :
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) :
print("\n Element not exists ", end = "")
else :
print("\n Exists in ", position ," position", end = "")

def main() :
#  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
#  Test A
#  X = 3
#  Test B
#  X = 1
#  Test C
#  X = 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)
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)
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)
print("\n Element not exists ")
else

print("\n Exists in ", position ," position")
end

end

end

def main()
#  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
#  Test A
#  X = 3
#  Test B
#  X = 1
#  Test C
#  X = 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)
{
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)
{
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)
{
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
// Test A
// X = 3
// Test B
// X = 1
// Test C
// X = 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)
{
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)
{
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)
{
print("\n Element not exists ", terminator: "");
}
else
{
print("\n Exists in ", position ," position", terminator: "");
}
}
}
func main()
{
// 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
// Test A
// X = 3
// Test B
// X = 1
// Test C
// X = 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)
{
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)
{
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)
{
print("\n Element not exists ");
}
else
{
print("\n Exists in " + position + " position");
}
}
}
fun main(args: Array < String > ): Unit
{
// 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
// Test A
// X = 3
// Test B
// X = 1
// Test C
// X = 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.

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

Categories
Relative Post