Skip to main content

Find fixed point in sorted array using recursion

A fixed point in a sorted array is an element whose value is equal to its index in the array. In other words, an element arr[i] is a fixed point if and only if i == arr[i].

Finding a fixed point in a sorted array using recursion involves dividing the array into two parts and recursively searching for a fixed point in one of the two parts. If the middle element of the array is a fixed point, the search can stop and the index of the fixed point can be returned. If the middle element is greater than its index, the fixed point must be in the left half of the array. Similarly, if the middle element is less than its index, the fixed point must be in the right half of the array.

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
Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment