Dada una array de n enteros 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, devuelva -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[] = {-10, -5, 2, 2, 2, 3, 4, 7, 9, 12, 13}
Output: 2 // arr[2] == 2
Input: arr[] = {-10, -5, 3, 4, 7, 9}
Output: -1 // No Fixed Point
Tenemos una solución para encontrar un punto fijo en una array de elementos distintos . En esta publicación, se analiza la solución para una array con valores duplicados.
Considere arr[] = {-10, -5, 2, 2, 2, 3, 4, 7, 9, 12, 13}, arr[mid] = 3 Si los elementos no son distintos, entonces vemos arr[
mid ] < mid, no podemos concluir de qué lado está el fijo. Puede ser del lado izquierdo o del lado derecho.
Sabemos con certeza que dado que arr[5] = 3, arr[4] no puede ser un índice mágico porque arr[4] debe ser menor o igual que arr[5] (la array está ordenada).
Entonces, el patrón general de nuestra búsqueda sería:
- Lado izquierdo: inicio = inicio, final = min (arr [índice medio], índice medio-1)
- Lado derecho: inicio = max(arr[midIndex], midIndex+1), end = end
A continuación se muestra el código para el algoritmo anterior.
C++
// CPP Program to find magic index.
#include <bits/stdc++.h>
using namespace std;
int magicIndex(int* arr, int start, int end)
{
// If No Magic Index return -1;
if (start > end)
return -1;
int midIndex = (start + end) / 2;
int midValue = arr[midIndex];
// Magic Index Found, return it.
if (midIndex == midValue)
return midIndex;
// Search on Left side
int left = magicIndex(arr, start, min(midValue,
midIndex - 1));
// If Found on left side, return.
if (left >= 0)
return left;
// Return ans from right side.
return magicIndex(arr, max(midValue, midIndex + 1),
end);
}
// Driver program
int main()
{
int arr[] = { -10, -5, 2, 2, 2, 3, 4, 7,
9, 12, 13 };
int n = sizeof(arr) / sizeof(arr[0]);
int index = magicIndex(arr, 0, n - 1);
if (index == -1)
cout << "No Magic Index";
else
cout << "Magic Index is : " << index;
return 0;
}
Java
// Java Program to find magic index.
class GFG {
static int magicIndex(int arr[], int start, int end)
{
// If No Magic Index return -1;
if (start > end)
return -1;
int midIndex = (start + end) / 2;
int midValue = arr[midIndex];
// Magic Index Found, return it.
if (midIndex == midValue)
return midIndex;
// Search on Left side
int left = magicIndex(arr, start, Math.min(midValue,
midIndex - 1));
// If Found on left side, return.
if (left >= 0)
return left;
// Return ans from right side.
return magicIndex(arr, Math.max(midValue,
midIndex + 1),end);
}
// Driver code
public static void main (String[] args)
{
int arr[] = { -10, -5, 2, 2, 2, 3, 4, 7,
9, 12, 13 };
int n = arr.length;
int index = magicIndex(arr, 0, n - 1);
if (index == -1)
System.out.print("No Magic Index");
else
System.out.print("Magic Index is : "+index);
}
}
// This code is contributed by Anant Agarwal.
Python 3
# Python 3 Program to find
# magic index.
def magicIndex(arr, start, end):
# If No Magic Index return -1
if (start > end):
return -1
midIndex = int((start + end) / 2)
midValue = arr[midIndex]
# Magic Index Found, return it.
if (midIndex == midValue):
return midIndex
# Search on Left side
left = magicIndex(arr, start, min(midValue,
midIndex - 1))
# If Found on left side, return.
if (left >= 0):
return left
# Return ans from right side.
return magicIndex(arr, max(midValue,
midIndex + 1),
end)
# Driver program
arr = [-10, -5, 2, 2, 2, 3, 4, 7, 9, 12, 13]
n = len(arr)
index = magicIndex(arr, 0, n - 1)
if (index == -1):
print("No Magic Index")
else:
print("Magic Index is :", index)
# This code is contributed by Smitha Dinesh Semwal
C#
// C# Program to find magic index.
using System;
class GFG {
static int magicIndex(int []arr, int start,
int end)
{
// If No Magic Index return -1;
if (start > end)
return -1;
int midIndex = (start + end) / 2;
int midValue = arr[midIndex];
// Magic Index Found, return it.
if (midIndex == midValue)
return midIndex;
// Search on Left side
int left = magicIndex(arr, start, Math.Min(midValue,
midIndex - 1));
// If Found on left side, return.
if (left >= 0)
return left;
// Return ans from right side.
return magicIndex(arr, Math.Max(midValue,
midIndex + 1),end);
}
// Driver code
public static void Main ()
{
int []arr = { -10, -5, 2, 2, 2, 3,
4, 7, 9, 12, 13 };
int n = arr.Length;
int index = magicIndex(arr, 0, n - 1);
if (index == -1)
Console.WriteLine("No Magic Index");
else
Console.WriteLine("Magic Index is : " +
index);
}
}
// This code is contributed by vt_m.
PHP
<?php
// PHP Program to find magic index.
function magicIndex($arr, $start, $end)
{
// If No Magic Index return -1;
if ($start > $end)
return -1;
$midIndex = floor(($start + $end) / 2);
$midValue = $arr[$midIndex];
// Magic Index Found, return it.
if ($midIndex == $midValue)
return $midIndex;
// Search on Left side
$left = magicIndex($arr, $start,
min($midValue, $midIndex - 1));
// If Found on left side, return.
if ($left >= 0)
return $left;
// Return ans from right side.
return magicIndex($arr, max($midValue,
$midIndex + 1), $end);
}
// Driver Code
$arr = array(-10, -5, 2, 2, 2, 3,
4, 7, 9, 12, 13);
$n = sizeof($arr);
$index = magicIndex($arr, 0, $n - 1);
if ($index == -1)
echo "No Magic Index";
else
echo "Magic Index is : " , $index;
// This code is contributed by nitin mittal
?>
Javascript
<script>
// JavaScript Program to find magic index.
function magicIndex(arr, start, end)
{
// If No Magic Index return -1;
if (start > end)
return -1;
let midIndex = Math.floor((start + end) / 2);
let midValue = arr[midIndex];
// Magic Index Found, return it.
if (midIndex == midValue)
return midIndex;
// Search on Left side
let left = magicIndex(arr, start, Math.min(midValue,
midIndex - 1));
// If Found on left side, return.
if (left >= 0)
return left;
// Return ans from right side.
return magicIndex(arr, Math.max(midValue, midIndex + 1),
end);
}
// Driver program
let arr = [ -10, -5, 2, 2, 2, 3, 4, 7,
9, 12, 13 ];
let n = arr.length;
let index = magicIndex(arr, 0, n - 1);
if (index == -1)
document.write("No Magic Index");
else
document.write("Magic Index is : " + index);
// This code is contributed by Surbhi Tyagi.
</script>
Producción:
Magic Index is : 2
Complejidad de tiempo: O(N)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por Aashish Chauhan y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA