Posted on by Kalkicode
Code Recursion

# Find fixed point in sorted array using recursion

The problem of finding a fixed point in a sorted array using recursion involves identifying an index in the array where the value is equal to the index itself. In other words, it requires finding an element in the array whose value matches its position.

## Problem Statement

Given a sorted array of integers, we need to implement a recursive algorithm to find the fixed point if one exists. If there are multiple fixed points, the algorithm will return any valid position. If no fixed point is found, the algorithm will indicate that none exists.

### Example

Let's consider the following sorted arrays:

1. `arr1 = [-1, -1, 1, 2, 4, 6, 7, 9, 10, 11, 13]` Result: Fixed point is at index 4 (value 4 matches the index).

2. `arr2 = [-1, 0, 1, 1, 3, 4, 6, 8, 10]` Result: Fixed point is at index 6 (value 6 matches the index).

3. `arr3 = [1, 2, 3, 4, 5, 6, 7]` Result: No fixed point exists in this array.

4. `arr4 = [-8, -6, 1, 2, 3, 5, 7, 9]` Result: Fixed point is at index 5 (value 5 matches the index).

## Algorithm and Pseudocode

1. The algorithm uses a recursive binary search approach to find the fixed point.
2. It checks the value at the middle index of the array and compares it with the index.
3. If the value matches the index, the function returns the index as the fixed point.
4. If the value is smaller than the index, the algorithm continues searching in the left half of the array.
5. If the value is larger than the index, the algorithm continues searching in the right half of the array.
6. The recursion continues until a fixed point is found or the search space is exhausted.

## Pseudocode

``````function findPosition(arr, start, end):
if end < start:
return -1
mid = (start + end) / 2
if arr[mid] == mid:
return mid
left_index = min(mid - 1, arr[mid])
result_left = findPosition(arr, start, left_index)
if result_left != -1:
return result_left
right_index = max(mid + 1, arr[mid])
return findPosition(arr, right_index, end)

function fixedPoint(arr, size):
location = findPosition(arr, 0, size - 1)
if location == -1:
print "None"
else:
print "Fixed point is", location
``````

## Program Solution

``````// 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)
{
// 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
*/
// Get the size of array2
size = arr2.length;
/*
Check B
arr  = [ -1, 0, 1, 1, 3, 4, 6, 8, 10]
ↆ
Fixed point

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

#### 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()
{
// 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
*/
// 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

*/
// Get the size of array3
size = sizeof(arr3) / sizeof(arr3[0]);
/*
Check C
arr  = [1, 2, 3, 4, 5, 6, 7]
*/
// Get the size of array4
size = sizeof(arr4) / sizeof(arr4[0]);
/*
Check D
arr  = [ -8, -6, 1, 2, 3, 5, 7, 9]
ↆ
Fixed point
*/
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
*/
// Get the size of array2
size = len(arr2)
/*
Check B
arr  = [ -1, 0, 1, 1, 3, 4, 6, 8, 10]
ↆ
Fixed point

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

#### 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)
{
// 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
*/
// Get the size of array2
size = arr2.Length;
/*
Check B
arr  = [ -1, 0, 1, 1, 3, 4, 6, 8, 10]
ↆ
Fixed point

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

#### 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()
{
// 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
*/
// Get the size of array2
\$size = count(\$arr2);
/*
Check B
arr  = [ -1, 0, 1, 1, 3, 4, 6, 8, 10]
ↆ
Fixed point

*/
// Get the size of array3
\$size = count(\$arr3);
/*
Check C
arr  = [1, 2, 3, 4, 5, 6, 7]
*/
// Get the size of array4
\$size = count(\$arr4);
/*
Check D
arr  = [ -8, -6, 1, 2, 3, 5, 7, 9]
ↆ
Fixed point
*/
}
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()
{
// 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
*/
// Get the size of array2
size = arr2.length;
/*
Check B
arr  = [ -1, 0, 1, 1, 3, 4, 6, 8, 10]
ↆ
Fixed point

*/
// Get the size of array3
size = arr3.length;
/*
Check C
arr  = [1, 2, 3, 4, 5, 6, 7]
*/
// Get the size of array4
size = arr4.length;
/*
Check D
arr  = [ -8, -6, 1, 2, 3, 5, 7, 9]
ↆ
Fixed point
*/
}
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() :
#  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
#  Get the size of list2
size = len(arr2)
#    Check B
#    arr  = [ -1, 0, 1, 1, 3, 4, 6, 8, 10]
#                                ↆ
#                            Fixed point
#  Get the size of list3
size = len(arr3)
#    Check C
#    arr  = [1, 2, 3, 4, 5, 6, 7]
#  Get the size of list4
size = len(arr4)
#    Check D
#    arr  = [ -8, -6, 1, 2, 3, 5, 7, 9]
#                              ↆ
#                          Fixed point

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()
#  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
#  Get the size of array2
size = arr2.length
#    Check B
#    arr  = [ -1, 0, 1, 1, 3, 4, 6, 8, 10]
#                                ↆ
#                            Fixed point
#  Get the size of array3
size = arr3.length
#    Check C
#    arr  = [1, 2, 3, 4, 5, 6, 7]
#  Get the size of array4
size = arr4.length
#    Check D
#    arr  = [ -8, -6, 1, 2, 3, 5, 7, 9]
#                              ↆ
#                          Fixed point
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
*/
// Get the size of array2
size = arr2.length;
/*
Check B
arr  = [ -1, 0, 1, 1, 3, 4, 6, 8, 10]
ↆ
Fixed point

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

#### 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()
{
// 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
*/
// Get the size of array2
size = arr2.count;
/*
Check B
arr  = [ -1, 0, 1, 1, 3, 4, 6, 8, 10]
ↆ
Fixed point

*/
// Get the size of array3
size = arr3.count;
/*
Check C
arr  = [1, 2, 3, 4, 5, 6, 7]
*/
// Get the size of array4
size = arr4.count;
/*
Check D
arr  = [ -8, -6, 1, 2, 3, 5, 7, 9]
ↆ
Fixed point
*/
}
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
{
// 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
*/
// Get the size of array2
size = arr2.count();
/*
Check B
arr  = [ -1, 0, 1, 1, 3, 4, 6, 8, 10]
ↆ
Fixed point

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

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

## Time Complexity

The time complexity of the recursive binary search algorithm for finding the fixed point in a sorted array is O(log n), where n is the number of elements in the array. This is because at each recursive step, the search space is divided in half.

## Output Explanation

For each given array, the algorithm correctly finds and prints the fixed point index if it exists. Otherwise, it indicates that no fixed point is present.

In this article, we explored the problem of finding a fixed point in a sorted array using recursion. We discussed the problem statement, provided examples, and presented an efficient recursive binary search algorithm to solve it. The pseudocode and time complexity were explained to understand the inner workings of the algorithm. The provided C code demonstrates the algorithm's correctness by producing the expected output for the given examples. By using recursion and binary search, we can efficiently solve this problem for large sorted arrays.

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