# Find fixed point in sorted array using recursion

Here given code implementation process.

``````// C Program
// Find fixed point in sorted array using recursion
#include <stdio.h>

// Function which is display array elements
void display(int arr[], int size)
{
for (int i = 0; i < size; ++i)
{
printf("%d ", arr[i]);
}
printf("\n");
}
// Returns a minimum value of two numbers
int minValue(int a, int b)
{
if (a < b)
{
return a;
}
return b;
}
// Returns a maximum value of two numbers
int maxValue(int a, int b)
{
if (a > b)
{
return a;
}
return b;
}
// By Using of binary search finding an element
// Which is exist as value of index.
int findPosition(int arr[], int s, int e)
{
if (e < s)
{
return -1;
}
int mid = (s + e) / 2;
if (mid == arr[mid])
{
// When index are same as its element value
return mid;
}
int index = minValue(mid - 1, arr[mid]);
index = findPosition(arr, s, index);
if (index != -1)
{
// When result found
return index;
}
index = maxValue(mid + 1, arr[mid]);
return findPosition(arr, index, e);
}
// Handles the request of finding fixed point in array
void fixedPoint(int arr[], int size)
{
// Display array element
printf("\n Array element : ");
display(arr, size);
int location = findPosition(arr, 0, size - 1);
if (location == -1)
{
//When no fixed point exists
printf(" None\n");
}
else
{
printf(" Fixed point is %d\n", location);
}
}
int main()
{
// Sorted array of integer elements
int arr1[] = {
-1 , -1 , 1 , 2 , 4 , 6 , 7 , 9 , 10 , 11 , 13
};
int arr2[] = {
-1 , 0 , 1 , 1 , 3 , 4 , 6 , 8 , 10
};
int arr3[] = {
1 , 2 , 3 , 4 , 5 , 6 , 7
};
int arr4[] = {
-8 , -6 , 1 , 2 , 3 , 5 , 7 , 9
};
// Get the size of array1
int size = sizeof(arr1) / sizeof(arr1[0]);
/*
Check A
arr  = [-1,-1, 1, 2, 4, 6, 7, 9, 10, 11, 13]
ↆ
Fixed point
*/
fixedPoint(arr1, size);
// Get the size of array2
size = sizeof(arr2) / sizeof(arr2[0]);
/*
Check B
arr  = [ -1, 0, 1, 1, 3, 4, 6, 8, 10]
ↆ
Fixed point

*/
fixedPoint(arr2, size);
// Get the size of array3
size = sizeof(arr3) / sizeof(arr3[0]);
/*
Check C
arr  = [1, 2, 3, 4, 5, 6, 7]
*/
fixedPoint(arr3, size);
// Get the size of array4
size = sizeof(arr4) / sizeof(arr4[0]);
/*
Check D
arr  = [ -8, -6, 1, 2, 3, 5, 7, 9]
ↆ
Fixed point
*/
fixedPoint(arr4, size);
return 0;
}``````

#### Output

`````` Array element : -1 -1 1 2 4 6 7 9 10 11 13
Fixed point is 4

Array element : -1 0 1 1 3 4 6 8 10
Fixed point is 6

Array element : 1 2 3 4 5 6 7
None

Array element : -8 -6 1 2 3 5 7 9
Fixed point is 5``````
``````// Java program for
// Find fixed point in sorted array using recursion
public class FixedLocation
{
// Function which is display array elements
public void display(int[] arr, int size)
{
for (int i = 0; i < size; ++i)
{
System.out.print("  " + arr[i]);
}
System.out.print("\n");
}
// Returns a minimum value of two numbers
public int minValue(int a, int b)
{
if (a < b)
{
return a;
}
return b;
}
// Returns a maximum value of two numbers
public int maxValue(int a, int b)
{
if (a > b)
{
return a;
}
return b;
}
// By Using of binary search finding an element
// Which is exist as value of index.
public int findPosition(int[] arr, int s, int e)
{
if (e < s)
{
return -1;
}
int mid = (s + e) / 2;
if (mid == arr[mid])
{
// When index are same as its element value
return mid;
}
int index = minValue(mid - 1, arr[mid]);
index = findPosition(arr, s, index);
if (index != -1)
{
// When result found
return index;
}
index = maxValue(mid + 1, arr[mid]);
return findPosition(arr, index, e);
}
// Handles the request of finding fixed point in array
public void fixedPoint(int[] arr, int size)
{
// Display array element
System.out.print("\n Array element : ");
display(arr, size);
int location = findPosition(arr, 0, size - 1);
if (location == -1)
{
//When no fixed point exists
System.out.print(" None\n");
}
else
{
System.out.print(" Fixed point is " + location + "\n");
}
}
public static void main(String[] args)
{
FixedLocation task = new FixedLocation();
// Sorted array of integer elements
int[] arr1 = {
-1 , -1 , 1 , 2 , 4 , 6 , 7 , 9 , 10 , 11 , 13
};
int[] arr2 = {
-1 , 0 , 1 , 1 , 3 , 4 , 6 , 8 , 10
};
int[] arr3 = {
1 , 2 , 3 , 4 , 5 , 6 , 7
};
int[] arr4 = {
-8 , -6 , 1 , 2 , 3 , 5 , 7 , 9
};
// Get the size of array1
int size = arr1.length;
/*
Check A
arr  = [-1,-1, 1, 2, 4, 6, 7, 9, 10, 11, 13]
ↆ
Fixed point
*/
task.fixedPoint(arr1, size);
// Get the size of array2
size = arr2.length;
/*
Check B
arr  = [ -1, 0, 1, 1, 3, 4, 6, 8, 10]
ↆ
Fixed point

*/
task.fixedPoint(arr2, size);
// Get the size of array3
size = arr3.length;
/*
Check C
arr  = [1, 2, 3, 4, 5, 6, 7]
*/
task.fixedPoint(arr3, size);
// Get the size of array4
size = arr4.length;
/*
Check D
arr  = [ -8, -6, 1, 2, 3, 5, 7, 9]
ↆ
Fixed point
*/
task.fixedPoint(arr4, size);
}
}``````

#### Output

`````` Array element :   -1  -1  1  2  4  6  7  9  10  11  13
Fixed point is 4

Array element :   -1  0  1  1  3  4  6  8  10
Fixed point is 6

Array element :   1  2  3  4  5  6  7
None

Array element :   -8  -6  1  2  3  5  7  9
Fixed point is 5``````
``````// Include header file
#include <iostream>

using namespace std;
// C++ program for
// Find fixed point in sorted array using recursion
class FixedLocation
{
public:
// Function which is display array elements
void display(int arr[], int size)
{
for (int i = 0; i < size; ++i)
{
cout << "  " << arr[i];
}
cout << "\n";
}
// Returns a minimum value of two numbers
int minValue(int a, int b)
{
if (a < b)
{
return a;
}
return b;
}
// Returns a maximum value of two numbers
int maxValue(int a, int b)
{
if (a > b)
{
return a;
}
return b;
}
// By Using of binary search finding an element
// Which is exist as value of index.
int findPosition(int arr[], int s, int e)
{
if (e < s)
{
return -1;
}
int mid = (s + e) / 2;
if (mid == arr[mid])
{
// When index are same as its element value
return mid;
}
int index = this->minValue(mid - 1, arr[mid]);
index = this->findPosition(arr, s, index);
if (index != -1)
{
// When result found
return index;
}
index = this->maxValue(mid + 1, arr[mid]);
return this->findPosition(arr, index, e);
}
// Handles the request of finding fixed point in array
void fixedPoint(int arr[], int size)
{
// Display array element
cout << "\n Array element : ";
this->display(arr, size);
int location = this->findPosition(arr, 0, size - 1);
if (location == -1)
{
//When no fixed point exists
cout << " None\n";
}
else
{
cout << " Fixed point is : " << location << "\n";
}
}
};
int main()
{
FixedLocation *task = new FixedLocation();
// Sorted array of integer elements
int arr1[] = {
-1 , -1 , 1 , 2 , 4 , 6 , 7 , 9 , 10 , 11 , 13
};
int arr2[] = {
-1 , 0 , 1 , 1 , 3 , 4 , 6 , 8 , 10
};
int arr3[] = {
1 , 2 , 3 , 4 , 5 , 6 , 7
};
int arr4[] = {
-8 , -6 , 1 , 2 , 3 , 5 , 7 , 9
};
// Get the size of array1
int size = sizeof(arr1) / sizeof(arr1[0]);
/*
Check A
arr  = [-1,-1, 1, 2, 4, 6, 7, 9, 10, 11, 13]
ↆ
Fixed point
*/
task->fixedPoint(arr1, size);
// Get the size of array2
size = sizeof(arr2) / sizeof(arr2[0]);
/*
Check B
arr  = [ -1, 0, 1, 1, 3, 4, 6, 8, 10]
ↆ
Fixed point

*/
task->fixedPoint(arr2, size);
// Get the size of array3
size = sizeof(arr3) / sizeof(arr3[0]);
/*
Check C
arr  = [1, 2, 3, 4, 5, 6, 7]
*/
task->fixedPoint(arr3, size);
// Get the size of array4
size = sizeof(arr4) / sizeof(arr4[0]);
/*
Check D
arr  = [ -8, -6, 1, 2, 3, 5, 7, 9]
ↆ
Fixed point
*/
task->fixedPoint(arr4, size);
return 0;
}``````

#### Output

`````` Array element :   -1  -1  1  2  4  6  7  9  10  11  13
Fixed point is : 4

Array element :   -1  0  1  1  3  4  6  8  10
Fixed point is : 6

Array element :   1  2  3  4  5  6  7
None

Array element :   -8  -6  1  2  3  5  7  9
Fixed point is : 5``````
``````package main
import "fmt"
// Go program for
// Find fixed point in sorted array using recursion
type FixedLocation struct {}
func getFixedLocation() * FixedLocation {
var me *FixedLocation = &FixedLocation {}
return me
}
// Function which is display array elements
func(this FixedLocation) display(arr[] int,
size int) {
for i := 0 ; i < size ; i++ {
fmt.Print("  ", arr[i])
}
fmt.Print("\n")
}
// Returns a minimum value of two numbers
func(this FixedLocation) minValue(a, b int) int {
if a < b {
return a
}
return b
}
// Returns a maximum value of two numbers
func(this FixedLocation) maxValue(a, b int) int {
if a > b {
return a
}
return b
}
// By Using of binary search finding an element
// Which is exist as value of index.
func(this FixedLocation) findPosition(arr[] int,
s int, e int) int {
if e < s {
return -1
}
var mid int = (s + e) / 2
if mid == arr[mid] {
// When index are same as its element value
return mid
}
var index int = this.minValue(mid - 1, arr[mid])
index = this.findPosition(arr, s, index)
if index != -1 {
// When result found
return index
}
index = this.maxValue(mid + 1, arr[mid])
return this.findPosition(arr, index, e)
}
// Handles the request of finding fixed point in array
func(this FixedLocation) fixedPoint(arr[] int, size int) {
// Display array element
fmt.Print("\n Array element : ")
this.display(arr, size)
var location int = this.findPosition(arr, 0, size - 1)
if location == -1 {
//When no fixed point exists
fmt.Print(" None\n")
} else {
fmt.Print(" Fixed point is : ", location, "\n")
}
}
func main() {
var task * FixedLocation = getFixedLocation()
// Sorted array of integer elements
var arr1 = [] int {-1, -1, 1, 2, 4, 6, 7, 9, 10, 11, 13}
var arr2 = [] int {-1, 0, 1, 1, 3, 4, 6, 8, 10}
var arr3 = [] int {1 , 2 , 3 , 4 , 5 , 6 , 7}
var arr4 = [] int {-8, -6, 1, 2, 3, 5, 7, 9}
// Get the size of array1
var size int = len(arr1)
/*
Check A
arr  = [-1,-1, 1, 2, 4, 6, 7, 9, 10, 11, 13]
ↆ
Fixed point
*/
task.fixedPoint(arr1, size)
// Get the size of array2
size = len(arr2)
/*
Check B
arr  = [ -1, 0, 1, 1, 3, 4, 6, 8, 10]
ↆ
Fixed point

*/
task.fixedPoint(arr2, size)
// Get the size of array3
size = len(arr3)
/*
Check C
arr  = [1, 2, 3, 4, 5, 6, 7]
*/
task.fixedPoint(arr3, size)
// Get the size of array4
size = len(arr4)
/*
Check D
arr  = [ -8, -6, 1, 2, 3, 5, 7, 9]
ↆ
Fixed point
*/
task.fixedPoint(arr4, size)
}``````

#### Output

`````` Array element :   -1  -1  1  2  4  6  7  9  10  11  13
Fixed point is : 4

Array element :   -1  0  1  1  3  4  6  8  10
Fixed point is : 6

Array element :   1  2  3  4  5  6  7
None

Array element :   -8  -6  1  2  3  5  7  9
Fixed point is : 5``````
``````// Include namespace system
using System;
// Csharp program for
// Find fixed point in sorted array using recursion
public class FixedLocation
{
// Function which is display array elements
public void display(int[] arr, int size)
{
for (int i = 0; i < size; ++i)
{
Console.Write("  " + arr[i]);
}
Console.Write("\n");
}
// Returns a minimum value of two numbers
public int minValue(int a, int b)
{
if (a < b)
{
return a;
}
return b;
}
// Returns a maximum value of two numbers
public int maxValue(int a, int b)
{
if (a > b)
{
return a;
}
return b;
}
// By Using of binary search finding an element
// Which is exist as value of index.
public int findPosition(int[] arr, int s, int e)
{
if (e < s)
{
return -1;
}
int mid = (s + e) / 2;
if (mid == arr[mid])
{
// When index are same as its element value
return mid;
}
int index = this.minValue(mid - 1, arr[mid]);
index = this.findPosition(arr, s, index);
if (index != -1)
{
// When result found
return index;
}
index = this.maxValue(mid + 1, arr[mid]);
return this.findPosition(arr, index, e);
}
// Handles the request of finding fixed point in array
public void fixedPoint(int[] arr, int size)
{
// Display array element
Console.Write("\n Array element : ");
this.display(arr, size);
int location = this.findPosition(arr, 0, size - 1);
if (location == -1)
{
//When no fixed point exists
Console.Write(" None\n");
}
else
{
Console.Write(" Fixed point is : " + location + "\n");
}
}
public static void Main(String[] args)
{
FixedLocation task = new FixedLocation();
// Sorted array of integer elements
int[] arr1 = {
-1 , -1 , 1 , 2 , 4 , 6 , 7 , 9 , 10 , 11 , 13
};
int[] arr2 = {
-1 , 0 , 1 , 1 , 3 , 4 , 6 , 8 , 10
};
int[] arr3 = {
1 , 2 , 3 , 4 , 5 , 6 , 7
};
int[] arr4 = {
-8 , -6 , 1 , 2 , 3 , 5 , 7 , 9
};
// Get the size of array1
int size = arr1.Length;
/*
Check A
arr  = [-1,-1, 1, 2, 4, 6, 7, 9, 10, 11, 13]
ↆ
Fixed point
*/
task.fixedPoint(arr1, size);
// Get the size of array2
size = arr2.Length;
/*
Check B
arr  = [ -1, 0, 1, 1, 3, 4, 6, 8, 10]
ↆ
Fixed point

*/
task.fixedPoint(arr2, size);
// Get the size of array3
size = arr3.Length;
/*
Check C
arr  = [1, 2, 3, 4, 5, 6, 7]
*/
task.fixedPoint(arr3, size);
// Get the size of array4
size = arr4.Length;
/*
Check D
arr  = [ -8, -6, 1, 2, 3, 5, 7, 9]
ↆ
Fixed point
*/
task.fixedPoint(arr4, size);
}
}``````

#### Output

`````` Array element :   -1  -1  1  2  4  6  7  9  10  11  13
Fixed point is : 4

Array element :   -1  0  1  1  3  4  6  8  10
Fixed point is : 6

Array element :   1  2  3  4  5  6  7
None

Array element :   -8  -6  1  2  3  5  7  9
Fixed point is : 5``````
``````<?php
// Php program for
// Find fixed point in sorted array using recursion
class FixedLocation
{
// Function which is display array elements
public	function display(\$arr, \$size)
{
for (\$i = 0; \$i < \$size; ++\$i)
{
echo("  ".\$arr[\$i]);
}
echo("\n");
}
// Returns a minimum value of two numbers
public	function minValue(\$a, \$b)
{
if (\$a < \$b)
{
return \$a;
}
return \$b;
}
// Returns a maximum value of two numbers
public	function maxValue(\$a, \$b)
{
if (\$a > \$b)
{
return \$a;
}
return \$b;
}
// By Using of binary search finding an element
// Which is exist as value of index.
public	function findPosition(\$arr, \$s, \$e)
{
if (\$e < \$s)
{
return -1;
}
\$mid = (int)((\$s + \$e) / 2);
if (\$mid == \$arr[\$mid])
{
// When index are same as its element value
return \$mid;
}
\$index = \$this->minValue(\$mid - 1, \$arr[\$mid]);
\$index = \$this->findPosition(\$arr, \$s, \$index);
if (\$index != -1)
{
// When result found
return \$index;
}
\$index = \$this->maxValue(\$mid + 1, \$arr[\$mid]);
return \$this->findPosition(\$arr, \$index, \$e);
}
// Handles the request of finding fixed point in array
public	function fixedPoint(\$arr, \$size)
{
// Display array element
echo("\n Array element : ");
\$this->display(\$arr, \$size);
\$location = \$this->findPosition(\$arr, 0, \$size - 1);
if (\$location == -1)
{
//When no fixed point exists
echo(" None\n");
}
else
{
echo(" Fixed point is : ".\$location.
"\n");
}
}
}

function main()
{
\$task = new FixedLocation();
// Sorted array of integer elements
\$arr1 = array(-1, -1, 1, 2, 4, 6, 7, 9, 10, 11, 13);
\$arr2 = array(-1, 0, 1, 1, 3, 4, 6, 8, 10);
\$arr3 = array(1, 2, 3, 4, 5, 6, 7);
\$arr4 = array(-8, -6, 1, 2, 3, 5, 7, 9);
// Get the size of array1
\$size = count(\$arr1);
/*
Check A
arr  = [-1,-1, 1, 2, 4, 6, 7, 9, 10, 11, 13]
ↆ
Fixed point
*/
\$task->fixedPoint(\$arr1, \$size);
// Get the size of array2
\$size = count(\$arr2);
/*
Check B
arr  = [ -1, 0, 1, 1, 3, 4, 6, 8, 10]
ↆ
Fixed point

*/
\$task->fixedPoint(\$arr2, \$size);
// Get the size of array3
\$size = count(\$arr3);
/*
Check C
arr  = [1, 2, 3, 4, 5, 6, 7]
*/
\$task->fixedPoint(\$arr3, \$size);
// Get the size of array4
\$size = count(\$arr4);
/*
Check D
arr  = [ -8, -6, 1, 2, 3, 5, 7, 9]
ↆ
Fixed point
*/
\$task->fixedPoint(\$arr4, \$size);
}
main();``````

#### Output

`````` Array element :   -1  -1  1  2  4  6  7  9  10  11  13
Fixed point is : 4

Array element :   -1  0  1  1  3  4  6  8  10
Fixed point is : 6

Array element :   1  2  3  4  5  6  7
None

Array element :   -8  -6  1  2  3  5  7  9
Fixed point is : 5``````
``````// Node JS program for
// Find fixed point in sorted array using recursion
class FixedLocation
{
// Function which is display array elements
display(arr, size)
{
for (var i = 0; i < size; ++i)
{
process.stdout.write("  " + arr[i]);
}
process.stdout.write("\n");
}
// Returns a minimum value of two numbers
minValue(a, b)
{
if (a < b)
{
return a;
}
return b;
}
// Returns a maximum value of two numbers
maxValue(a, b)
{
if (a > b)
{
return a;
}
return b;
}
// By Using of binary search finding an element
// Which is exist as value of index.
findPosition(arr, s, e)
{
if (e < s)
{
return -1;
}
var mid = parseInt((s + e) / 2);
if (mid == arr[mid])
{
// When index are same as its element value
return mid;
}
var index = this.minValue(mid - 1, arr[mid]);
index = this.findPosition(arr, s, index);
if (index != -1)
{
// When result found
return index;
}
index = this.maxValue(mid + 1, arr[mid]);
return this.findPosition(arr, index, e);
}
// Handles the request of finding fixed point in array
fixedPoint(arr, size)
{
// Display array element
process.stdout.write("\n Array element : ");
this.display(arr, size);
var location = this.findPosition(arr, 0, size - 1);
if (location == -1)
{
//When no fixed point exists
process.stdout.write(" None\n");
}
else
{
process.stdout.write(" Fixed point is : " +
location + "\n");
}
}
}

function main()
{
var task = new FixedLocation();
// Sorted array of integer elements
var arr1 = [-1, -1, 1, 2, 4, 6, 7, 9, 10, 11, 13];
var arr2 = [-1, 0, 1, 1, 3, 4, 6, 8, 10];
var arr3 = [1, 2, 3, 4, 5, 6, 7];
var arr4 = [-8, -6, 1, 2, 3, 5, 7, 9];
// Get the size of array1
var size = arr1.length;
/*
Check A
arr  = [-1,-1, 1, 2, 4, 6, 7, 9, 10, 11, 13]
ↆ
Fixed point
*/
task.fixedPoint(arr1, size);
// Get the size of array2
size = arr2.length;
/*
Check B
arr  = [ -1, 0, 1, 1, 3, 4, 6, 8, 10]
ↆ
Fixed point

*/
task.fixedPoint(arr2, size);
// Get the size of array3
size = arr3.length;
/*
Check C
arr  = [1, 2, 3, 4, 5, 6, 7]
*/
task.fixedPoint(arr3, size);
// Get the size of array4
size = arr4.length;
/*
Check D
arr  = [ -8, -6, 1, 2, 3, 5, 7, 9]
ↆ
Fixed point
*/
task.fixedPoint(arr4, size);
}
main();``````

#### Output

`````` Array element :   -1  -1  1  2  4  6  7  9  10  11  13
Fixed point is : 4

Array element :   -1  0  1  1  3  4  6  8  10
Fixed point is : 6

Array element :   1  2  3  4  5  6  7
None

Array element :   -8  -6  1  2  3  5  7  9
Fixed point is : 5``````
``````#  Python 3 program for
#  Find fixed point in sorted array using recursion
class FixedLocation :
#  Function which is display list elements
def display(self, arr, size) :
i = 0
while (i < size) :
print("  ", arr[i], end = "",sep="")
i += 1

print(end = "\n")

#  Returns a minimum value of two numbers
def minValue(self, a, b) :
if (a < b) :
return a

return b

#  Returns a maximum value of two numbers
def maxValue(self, a, b) :
if (a > b) :
return a

return b

#  By Using of binary search finding an element
#  Which is exist as value of index.
def findPosition(self, arr, s, e) :
if (e < s) :
return -1

mid = int((s + e) / 2)
if (mid == arr[mid]) :
#  When index are same as its element value
return mid

index = self.minValue(mid - 1, arr[mid])
index = self.findPosition(arr, s, index)
if (index != -1) :
#  When result found
return index

index = self.maxValue(mid + 1, arr[mid])
return self.findPosition(arr, index, e)

#  Handles the request of finding fixed point in list
def fixedPoint(self, arr, size) :
#  Display list element
print("\n Array element : ", end = "")
self.display(arr, size)
location = self.findPosition(arr, 0, size - 1)
if (location == -1) :
# When no fixed point exists
print(" None")
else :
print(" Fixed point is : ", location )

def main() :
task = FixedLocation()
#  Sorted list of integer elements
arr1 = [-1, -1, 1, 2, 4, 6, 7, 9, 10, 11, 13]
arr2 = [-1, 0, 1, 1, 3, 4, 6, 8, 10]
arr3 = [1, 2, 3, 4, 5, 6, 7]
arr4 = [-8, -6, 1, 2, 3, 5, 7, 9]
#  Get the size of list1
size = len(arr1)
#    Check A
#    arr  = [-1,-1, 1, 2, 4, 6, 7, 9, 10, 11, 13]
#                         ↆ
#                     Fixed point
task.fixedPoint(arr1, size)
#  Get the size of list2
size = len(arr2)
#    Check B
#    arr  = [ -1, 0, 1, 1, 3, 4, 6, 8, 10]
#                                ↆ
#                            Fixed point
task.fixedPoint(arr2, size)
#  Get the size of list3
size = len(arr3)
#    Check C
#    arr  = [1, 2, 3, 4, 5, 6, 7]
task.fixedPoint(arr3, size)
#  Get the size of list4
size = len(arr4)
#    Check D
#    arr  = [ -8, -6, 1, 2, 3, 5, 7, 9]
#                              ↆ
#                          Fixed point
task.fixedPoint(arr4, size)

if __name__ == "__main__": main()``````

#### Output

`````` Array element :   -1  -1  1  2  4  6  7  9  10  11  13
Fixed point is :  4

Array element :   -1  0  1  1  3  4  6  8  10
Fixed point is :  6

Array element :   1  2  3  4  5  6  7
None

Array element :   -8  -6  1  2  3  5  7  9
Fixed point is :  5``````
``````#  Ruby program for
#  Find fixed point in sorted array using recursion
class FixedLocation
#  Function which is display array elements
def display(arr, size)
i = 0
while (i < size)
print("  ", arr[i])
i += 1
end

print("\n")
end

#  Returns a minimum value of two numbers
def minValue(a, b)
if (a < b)
return a
end

return b
end

#  Returns a maximum value of two numbers
def maxValue(a, b)
if (a > b)
return a
end

return b
end

#  By Using of binary search finding an element
#  Which is exist as value of index.
def findPosition(arr, s, e)
if (e < s)
return -1
end

mid = (s + e) / 2
if (mid == arr[mid])
#  When index are same as its element value
return mid
end

index = self.minValue(mid - 1, arr[mid])
index = self.findPosition(arr, s, index)
if (index != -1)
#  When result found
return index
end

index = self.maxValue(mid + 1, arr[mid])
return self.findPosition(arr, index, e)
end

#  Handles the request of finding fixed point in array
def fixedPoint(arr, size)
#  Display array element
print("\n Array element : ")
self.display(arr, size)
location = self.findPosition(arr, 0, size - 1)
if (location == -1)
# When no fixed point exists
print(" None\n")
else

print(" Fixed point is : ", location ,"\n")
end

end

end

def main()
task = FixedLocation.new()
#  Sorted array of integer elements
arr1 = [-1, -1, 1, 2, 4, 6, 7, 9, 10, 11, 13]
arr2 = [-1, 0, 1, 1, 3, 4, 6, 8, 10]
arr3 = [1, 2, 3, 4, 5, 6, 7]
arr4 = [-8, -6, 1, 2, 3, 5, 7, 9]
#  Get the size of array1
size = arr1.length
#    Check A
#    arr  = [-1,-1, 1, 2, 4, 6, 7, 9, 10, 11, 13]
#                         ↆ
#                     Fixed point
task.fixedPoint(arr1, size)
#  Get the size of array2
size = arr2.length
#    Check B
#    arr  = [ -1, 0, 1, 1, 3, 4, 6, 8, 10]
#                                ↆ
#                            Fixed point
task.fixedPoint(arr2, size)
#  Get the size of array3
size = arr3.length
#    Check C
#    arr  = [1, 2, 3, 4, 5, 6, 7]
task.fixedPoint(arr3, size)
#  Get the size of array4
size = arr4.length
#    Check D
#    arr  = [ -8, -6, 1, 2, 3, 5, 7, 9]
#                              ↆ
#                          Fixed point
task.fixedPoint(arr4, size)
end

main()``````

#### Output

`````` Array element :   -1  -1  1  2  4  6  7  9  10  11  13
Fixed point is : 4

Array element :   -1  0  1  1  3  4  6  8  10
Fixed point is : 6

Array element :   1  2  3  4  5  6  7
None

Array element :   -8  -6  1  2  3  5  7  9
Fixed point is : 5
``````
``````// Scala program for
// Find fixed point in sorted array using recursion
class FixedLocation()
{
// Function which is display array elements
def display(arr: Array[Int], size: Int): Unit = {
var i: Int = 0;
while (i < size)
{
print("  " + arr(i));
i += 1;
}
print("\n");
}
// Returns a minimum value of two numbers
def minValue(a: Int, b: Int): Int = {
if (a < b)
{
return a;
}
return b;
}
// Returns a maximum value of two numbers
def maxValue(a: Int, b: Int): Int = {
if (a > b)
{
return a;
}
return b;
}
// By Using of binary search finding an element
// Which is exist as value of index.
def findPosition(arr: Array[Int], s: Int, e: Int): Int = {
if (e < s)
{
return -1;
}
var mid: Int = (s + e) / 2;
if (mid == arr(mid))
{
// When index are same as its element value
return mid;
}
var index: Int = minValue(mid - 1, arr(mid));
index = findPosition(arr, s, index);
if (index != -1)
{
// When result found
return index;
}
index = maxValue(mid + 1, arr(mid));
return findPosition(arr, index, e);
}
// Handles the request of finding fixed point in array
def fixedPoint(arr: Array[Int], size: Int): Unit = {
// Display array element
print("\n Array element : ");
display(arr, size);
var location: Int = findPosition(arr, 0, size - 1);
if (location == -1)
{
//When no fixed point exists
print(" None\n");
}
else
{
print(" Fixed point is : " + location + "\n");
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: FixedLocation = new FixedLocation();
// Sorted array of integer elements
var arr1: Array[Int] = Array(-1, -1, 1, 2, 4, 6, 7, 9, 10, 11, 13);
var arr2: Array[Int] = Array(-1, 0, 1, 1, 3, 4, 6, 8, 10);
var arr3: Array[Int] = Array(1, 2, 3, 4, 5, 6, 7);
var arr4: Array[Int] = Array(-8, -6, 1, 2, 3, 5, 7, 9);
// Get the size of array1
var size: Int = arr1.length;
/*
Check A
arr  = [-1,-1, 1, 2, 4, 6, 7, 9, 10, 11, 13]
ↆ
Fixed point
*/
task.fixedPoint(arr1, size);
// Get the size of array2
size = arr2.length;
/*
Check B
arr  = [ -1, 0, 1, 1, 3, 4, 6, 8, 10]
ↆ
Fixed point

*/
task.fixedPoint(arr2, size);
// Get the size of array3
size = arr3.length;
/*
Check C
arr  = [1, 2, 3, 4, 5, 6, 7]
*/
task.fixedPoint(arr3, size);
// Get the size of array4
size = arr4.length;
/*
Check D
arr  = [ -8, -6, 1, 2, 3, 5, 7, 9]
ↆ
Fixed point
*/
task.fixedPoint(arr4, size);
}
}``````

#### Output

`````` Array element :   -1  -1  1  2  4  6  7  9  10  11  13
Fixed point is : 4

Array element :   -1  0  1  1  3  4  6  8  10
Fixed point is : 6

Array element :   1  2  3  4  5  6  7
None

Array element :   -8  -6  1  2  3  5  7  9
Fixed point is : 5``````
``````import Foundation;
// Swift 4 program for
// Find fixed point in sorted array using recursion
class FixedLocation
{
// Function which is display array elements
func display(_ arr: [Int], _ size: Int)
{
var i: Int = 0;
while (i < size)
{
print("  ", arr[i], terminator: "");
i += 1;
}
print(terminator: "\n");
}
// Returns a minimum value of two numbers
func minValue(_ a: Int, _ b: Int) -> Int
{
if (a < b)
{
return a;
}
return b;
}
// Returns a maximum value of two numbers
func maxValue(_ a: Int, _ b: Int) -> Int
{
if (a > b)
{
return a;
}
return b;
}
// By Using of binary search finding an element
// Which is exist as value of index.
func findPosition(_ arr: [Int], _ s: Int, _ e: Int) -> Int
{
if (e < s)
{
return -1;
}
let mid: Int = (s + e) / 2;
if (mid == arr[mid])
{
// When index are same as its element value
return mid;
}
var index: Int = self.minValue(mid - 1, arr[mid]);
index = self.findPosition(arr, s, index);
if (index  != -1)
{
// When result found
return index;
}
index = self.maxValue(mid + 1, arr[mid]);
return self.findPosition(arr, index, e);
}
// Handles the request of finding fixed point in array
func fixedPoint(_ arr: [Int], _ size: Int)
{
// Display array element
print("\n Array element : ", terminator: "");
self.display(arr, size);
let location: Int = self.findPosition(arr, 0, size - 1);
if (location == -1)
{
//When no fixed point exists
print(" None");
}
else
{
print(" Fixed point is : ", location );
}
}
}
func main()
{
let task: FixedLocation = FixedLocation();
// Sorted array of integer elements
let arr1: [Int] = [-1, -1, 1, 2, 4, 6, 7, 9, 10, 11, 13];
let arr2: [Int] = [-1, 0, 1, 1, 3, 4, 6, 8, 10];
let arr3: [Int] = [1, 2, 3, 4, 5, 6, 7];
let arr4: [Int] = [-8, -6, 1, 2, 3, 5, 7, 9];
// Get the size of array1
var size: Int = arr1.count;
/*
Check A
arr  = [-1,-1, 1, 2, 4, 6, 7, 9, 10, 11, 13]
ↆ
Fixed point
*/
task.fixedPoint(arr1, size);
// Get the size of array2
size = arr2.count;
/*
Check B
arr  = [ -1, 0, 1, 1, 3, 4, 6, 8, 10]
ↆ
Fixed point

*/
task.fixedPoint(arr2, size);
// Get the size of array3
size = arr3.count;
/*
Check C
arr  = [1, 2, 3, 4, 5, 6, 7]
*/
task.fixedPoint(arr3, size);
// Get the size of array4
size = arr4.count;
/*
Check D
arr  = [ -8, -6, 1, 2, 3, 5, 7, 9]
ↆ
Fixed point
*/
task.fixedPoint(arr4, size);
}
main();``````

#### Output

`````` Array element :    -1   -1   1   2   4   6   7   9   10   11   13
Fixed point is :  4

Array element :    -1   0   1   1   3   4   6   8   10
Fixed point is :  6

Array element :    1   2   3   4   5   6   7
None

Array element :    -8   -6   1   2   3   5   7   9
Fixed point is :  5``````
``````// Kotlin program for
// Find fixed point in sorted array using recursion
class FixedLocation
{
// Function which is display array elements
fun display(arr: Array < Int > , size: Int): Unit
{
var i: Int = 0;
while (i < size)
{
print("  " + arr[i]);
i += 1;
}
print("\n");
}
// Returns a minimum value of two numbers
fun minValue(a: Int, b: Int): Int
{
if (a < b)
{
return a;
}
return b;
}
// Returns a maximum value of two numbers
fun maxValue(a: Int, b: Int): Int
{
if (a > b)
{
return a;
}
return b;
}
// By Using of binary search finding an element
// Which is exist as value of index.
fun findPosition(arr: Array < Int > , s: Int, e: Int): Int
{
if (e < s)
{
return -1;
}
val mid: Int = (s + e) / 2;
if (mid == arr[mid])
{
// When index are same as its element value
return mid;
}
var index: Int = this.minValue(mid - 1, arr[mid]);
index = this.findPosition(arr, s, index);
if (index != -1)
{
// When result found
return index;
}
index = this.maxValue(mid + 1, arr[mid]);
return this.findPosition(arr, index, e);
}
// Handles the request of finding fixed point in array
fun fixedPoint(arr: Array < Int > , size: Int): Unit
{
// Display array element
print("\n Array element : ");
this.display(arr, size);
val location: Int = this.findPosition(arr, 0, size - 1);
if (location == -1)
{
//When no fixed point exists
print(" None\n");
}
else
{
print(" Fixed point is : " + location + "\n");
}
}
}
fun main(args: Array < String > ): Unit
{
val task: FixedLocation = FixedLocation();
// Sorted array of integer elements
val arr1: Array < Int > = arrayOf(-1, -1, 1, 2, 4, 6, 7, 9, 10, 11, 13);
val arr2: Array < Int > = arrayOf(-1, 0, 1, 1, 3, 4, 6, 8, 10);
val arr3: Array < Int > = arrayOf(1, 2, 3, 4, 5, 6, 7);
val arr4: Array < Int > = arrayOf(-8, -6, 1, 2, 3, 5, 7, 9);
// Get the size of array1
var size: Int = arr1.count();
/*
Check A
arr  = [-1,-1, 1, 2, 4, 6, 7, 9, 10, 11, 13]
ↆ
Fixed point
*/
task.fixedPoint(arr1, size);
// Get the size of array2
size = arr2.count();
/*
Check B
arr  = [ -1, 0, 1, 1, 3, 4, 6, 8, 10]
ↆ
Fixed point

*/
task.fixedPoint(arr2, size);
// Get the size of array3
size = arr3.count();
/*
Check C
arr  = [1, 2, 3, 4, 5, 6, 7]
*/
task.fixedPoint(arr3, size);
// Get the size of array4
size = arr4.count();
/*
Check D
arr  = [ -8, -6, 1, 2, 3, 5, 7, 9]
ↆ
Fixed point
*/
task.fixedPoint(arr4, size);
}``````

#### Output

`````` Array element :   -1  -1  1  2  4  6  7  9  10  11  13
Fixed point is : 4

Array element :   -1  0  1  1  3  4  6  8  10
Fixed point is : 6

Array element :   1  2  3  4  5  6  7
None

Array element :   -8  -6  1  2  3  5  7  9
Fixed point is : 5``````

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

© 2022, kalkicode.com, All rights reserved