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)
	{
		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

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.

New Comment