Dada una array de n enteros distintos ordenados en orden ascendente, escriba una función que devuelva un punto fijo en la array, si hay algún punto fijo presente en la array, de lo contrario, devuelve -1. Punto fijo en una array es un índice i tal que arr[i] es igual a i. Tenga en cuenta que los enteros en la array pueden ser negativos.
Ejemplos:
Input: arr[] = {-10, -5, 0, 3, 7}
Output: 3 // arr[3] == 3
Input: arr[] = {0, 2, 5, 8, 17}
Output: 0 // arr[0] == 0
Input: arr[] = {-10, -5, 3, 4, 7, 9}
Output: -1 // No Fixed Point
Método 1 (búsqueda lineal)
Búsqueda lineal de un índice i tal que arr[i] == i. Devuelve el primer índice de este tipo encontrado. Gracias a pm por sugerir esta solución.
C++
// C++ program to check fixed point
// in an array using linear search
#include <bits/stdc++.h>
using namespace std;
int linearSearch(int arr[], int n)
{
int i;
for (i = 0; i < n; i++) {
if (arr[i] == i)
return i;
}
/* If no fixed point present then return -1 */
return -1;
}
/* Driver code */
int main()
{
int arr[] = { -10, -1, 0, 3, 10, 11, 30, 50, 100 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Fixed Point is " << linearSearch(arr, n);
return 0;
}
// This is code is contributed by rathbhupendra
C
// C program to check fixed point
// in an array using linear search
#include <stdio.h>
int linearSearch(int arr[], int n)
{
int i;
for (i = 0; i < n; i++) {
if (arr[i] == i)
return i;
}
/* If no fixed point present then return -1 */
return -1;
}
/* Driver program to check above functions */
int main()
{
int arr[] = { -10, -1, 0, 3, 10, 11, 30, 50, 100 };
int n = sizeof(arr) / sizeof(arr[0]);
printf("Fixed Point is %d", linearSearch(arr, n));
getchar();
return 0;
}
Java
// Java program to check fixed point
// in an array using linear search
class Main {
static int linearSearch(int arr[], int n)
{
int i;
for (i = 0; i < n; i++) {
if (arr[i] == i)
return i;
}
/* If no fixed point present
then return -1 */
return -1;
}
// main function
public static void main(String args[])
{
int arr[] = { -10, -1, 0, 3, 10, 11, 30, 50, 100 };
int n = arr.length;
System.out.println("Fixed Point is "
+ linearSearch(arr, n));
}
}
Python3
# Python program to check fixed point
# in an array using linear search
def linearSearch(arr, n):
for i in range(n):
if arr[i] is i:
return i
# If no fixed point present then return -1
return -1
# Driver program to check above functions
arr = [-10, -1, 0, 3, 10, 11, 30, 50, 100]
n = len(arr)
print("Fixed Point is " + str(linearSearch(arr, n)))
# This code is contributed by Pratik Chhajer
C#
// C# program to check fixed point
// in an array using linear search
using System;
class GFG {
static int linearSearch(int[] arr, int n)
{
int i;
for (i = 0; i < n; i++) {
if (arr[i] == i)
return i;
}
/* If no fixed point present
then return -1 */
return -1;
}
// Driver code
public static void Main()
{
int[] arr = { -10, -1, 0, 3, 10, 11, 30, 50, 100 };
int n = arr.Length;
Console.Write("Fixed Point is " + linearSearch(arr, n));
}
}
// This code is contributed by Sam007
PHP
<?php
// PHP program to check fixed point
// in an array using linear search
function linearSearch($arr, $n)
{
for($i = 0; $i < $n; $i++)
{
if($arr[$i] == $i)
return $i;
}
// If no fixed point present then
// return -1
return -1;
}
// Driver Code
$arr = array(-10, -1, 0, 3, 10,
11, 30, 50, 100);
$n = count($arr);
echo "Fixed Point is ".
linearSearch($arr, $n);
// This code is contributed by Sam007
?>
Javascript
<script>
// JavaScript program to check fixed point
// in an array using linear search
function linearSearch(arr, n)
{
let i;
for(i = 0; i < n; i++)
{
if(arr[i] == i)
return i;
}
/* If no fixed point present
then return -1 */
return -1;
}
// Driver Code
let arr = [-10, -1, 0, 3, 10, 11, 30, 50, 100];
let n = arr.length;
document.write("Fixed Point is "
+ linearSearch(arr, n));
</script>
Producción:
Fixed Point is 3
Complejidad temporal: O(n)
Espacio auxiliar: O(1)
Método 2 (búsqueda binaria)
Primero verifique si el elemento central es punto fijo o no. Si es así, devuélvelo; de lo contrario, si el índice del elemento medio + 1 es menor o igual que el valor en el índice alto, entonces los puntos fijos podrían estar en el lado derecho del punto medio (obviamente solo si hay un punto fijo). De manera similar, verifique si el índice del elemento medio – 1 es mayor o igual que el valor en el índice bajo, entonces los puntos fijos podrían estar en el lado izquierdo del punto medio.
C++
// C++ program to check fixed point
// in an array using binary search
#include <bits/stdc++.h>
using namespace std;
int binarySearch(int arr[], int low, int high)
{
if (high >= low) {
int mid = low + (high - low) / 2;
if (mid == arr[mid])
return mid;
int res = -1;
if (mid + 1 <= arr[high])
res = binarySearch(arr, (mid + 1), high);
if (res != -1)
return res;
if (mid - 1 >= arr[low])
return binarySearch(arr, low, (mid - 1));
}
/* Return -1 if there is no Fixed Point */
return -1;
}
/* Driver code */
int main()
{
int arr[10] = { -10, -1, 0, 3, 10, 11, 30, 50, 100 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Fixed Point is " << binarySearch(arr, 0, n - 1);
return 0;
}
// This code is contributed by Ashutosh Singh
C
// C program to check fixed point
// in an array using binary search
#include <stdio.h>
int binarySearch(int arr[], int low, int high)
{
if (high >= low) {
int mid = low + (high - low) / 2;
if (mid == arr[mid])
return mid;
int res = -1;
if (mid + 1 <= arr[high])
res = binarySearch(arr, (mid + 1), high);
if (res != -1)
return res;
if (mid - 1 >= arr[low])
return binarySearch(arr, low, (mid - 1));
}
/* Return -1 if there is no Fixed Point */
return -1;
}
/* Driver program to check above functions */
int main()
{
int arr[10] = { -10, -1, 0, 3, 10, 11, 30, 50, 100 };
int n = sizeof(arr) / sizeof(arr[0]);
printf("Fixed Point is %d", binarySearch(arr, 0, n - 1));
getchar();
return 0;
}
Java
// Java program to check fixed point
// in an array using binary search
class Main {
static int binarySearch(int arr[], int low, int high)
{
if (high >= low) {
int mid = low + (high - low) / 2;
if (mid == arr[mid])
return mid;
int res = -1;
if (mid + 1 <= arr[high])
res = binarySearch(arr, (mid + 1), high);
if (res != -1)
return res;
if (mid - 1 >= arr[low])
return binarySearch(arr, low, (mid - 1));
}
/* Return -1 if there is no Fixed Point */
return -1;
}
// main function
public static void main(String args[])
{
int arr[] = { -10, -1, 0, 3, 10, 11, 30, 50, 100 };
int n = arr.length;
System.out.println("Fixed Point is "
+ binarySearch(arr, 0, n - 1));
}
}
Python3
# Python program to check fixed point
# in an array using binary search
def binarySearch(arr, low, high):
if high >= low :
mid = low + (high - low)//2
if mid == arr[mid]:
return mid
res = -1
if mid + 1 <= arr[high]:
res = binarySearch(arr, (mid + 1), high)
if res !=-1:
return res
if mid-1 >= arr[low]:
return binarySearch(arr, low, (mid -1))
# Return -1 if there is no Fixed Point
return -1
# Driver program to check above functions */
arr = [-10, -1, 0, 3, 10, 11, 30, 50, 100]
n = len(arr)
print("Fixed Point is " + str(binarySearch(arr, 0, n-1)))
C#
// C# program to check fixed point
// in an array using binary search
using System;
class GFG {
static int binarySearch(int[] arr, int low, int high)
{
if (high >= low) {
int mid = low + (high - low) / 2;
if (mid == arr[mid])
return mid;
int res = -1;
if (mid + 1 <= arr[high])
res = binarySearch(arr, (mid + 1), high);
if (res != -1)
return res;
if (mid - 1 >= arr[low])
return binarySearch(arr, low, (mid - 1));
}
/* Return -1 if there is no Fixed Point */
return -1;
}
// Driver code
public static void Main()
{
int[] arr = { -10, -1, 0, 3, 10, 11, 30, 50, 100 };
int n = arr.Length;
Console.Write("Fixed Point is " + binarySearch(arr, 0, n - 1));
}
}
PHP
<?php
// PHP program to check fixed point
// in an array using binary search
function binarySearch($arr, $low, $high)
{
if($high >= $low)
{
$mid = (int)($low + ($high - $low)/2);
if($mid == $arr[$mid])
return $mid;
$res = -1;
if($mid+1 <= $arr[$high])
$res = binarySearch($arr, ($mid + 1), $high);
if($res!=-1)
return $res;
if($mid-1 >= $arr[$low])
return binarySearch($arr, $low, ($mid -1));
}
/* Return -1 if there is no Fixed Point */
return -1;
}
// Driver Code
$arr = array(-10, -1, 0, 3, 10,
11, 30, 50, 100);
$n = count($arr);
echo "Fixed Point is: "
. binarySearch($arr, 0, $n - 1);
?>
Javascript
<script>
// javascript program to check fixed point
// in an array using binary search
function binarySearch(arr,low,high)
{
if(high >= low)
{
let mid = math.floor(low + (high - low)/2);
if(mid == arr[mid])
return mid;
let res = -1;
if(mid+1 <= arr[high])
res = binarySearch(arr, (mid + 1), high);
if(res!=-1)
return res;
if(mid-1 >= arr[low])
return binarySearch(arr, low, (mid -1));
}
/* Return -1 if there is no Fixed Point */
return -1;
}
// Driver program
let arr = [-10, -1, 0, 3, 10, 11, 30, 50, 100];
let n = arr.length;
document.write("Fixed Point is "+ binarySearch(arr, 0, n-1));
</script>
Producción:
Fixed Point is 3
Paradigma algorítmico: divide y vencerás
Complejidad de tiempo: O (log n)
Espacio auxiliar : O (log n) (ya que la pila implícita se usa para llamadas recursivas)
Encuentre un punto fijo (valor igual al índice) en una array dada | Se permiten duplicados
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA