Dada una array de n duplicados o 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, -1, 3, 3, 10, 30, 30, 50, 100}
Output: 3
Note : arr[3] == 3
Input: arr[] = {0, 2, 5, 8, 17}
Output: 0
Input: arr[] = {-10, -5, 3, 4, 7, 9}
Output: -1
No Fixed Point
Ya hemos discutido encontrar un punto fijo en una array dada de n enteros distintos .
Si los elementos no son distintos, el algoritmo discutido anteriormente falla. Considere la siguiente array:
// with duplicates value
Input : arr[] = {-10, -5, 2, 2, 2, 3, 4, 7, 9, 12, 13};
Wrong Output : -1 // but arr[2] == 2
Cuando vemos que A [mid] < mid, no podemos concluir de qué lado está el índice fijo. Podría estar en el lado derecho, como antes. O bien, podría estar en el lado izquierdo (como, de hecho, es).
¿Podría estar en cualquier parte del lado izquierdo? No exactamente. Como A[ 5] = 3, sabemos que A[ 4] no puede ser un índice fijo. A[ 4] tendría que ser 4 para ser el índice fijo, pero A[ 4] debe ser menor o igual que A[ 5].
De hecho, cuando veamos que A[ 5] = 3, necesitaremos buscar recursivamente en el lado derecho como antes. Pero, para buscar en el lado izquierdo, podemos omitir un montón de elementos y solo buscar de forma recursiva los elementos A [ 0] a A [ 3]. A[ 3] es el primer elemento que podría ser un índice fijo.
El patrón general es que primero comparamos mid Index y midValue para la igualdad. Luego, si no son iguales, buscamos recursivamente los lados izquierdo y derecho de la siguiente manera:
Implementación:
C++
// C++ implementation to find fixed
// index using binary search
#include<bits/stdc++.h>
using namespace std;
// Main Function to find fixed
// index using binary search
int binarySearch(int arr[], int low,
int high)
{
if (high < low)
return -1;
// low + (high - low) / 2
int mid = (low + high) / 2;
int midValue = arr[mid];
if (mid == arr[mid])
return mid;
// Search left
int leftindex = min(mid - 1, midValue);
int left = binarySearch(arr, low, leftindex);
if (left >= 0)
return left;
// Search right
int rightindex = max(mid + 1, midValue);
int right = binarySearch(arr, rightindex, high);
return right;
}
// Driver code
int main()
{
// input 1
int arr[] = {-10, -5, 2, 2, 2,
3, 4, 7, 9, 12, 13};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Fixed Point is "
<< binarySearch(arr, 0, n - 1);
// input 2
int arr1[] = {-10, -1, 3, 3, 10,
30, 30, 50, 100};
int n1 = sizeof(arr) / sizeof(arr1[0]);
cout << "\nFixed Point is "
<< binarySearch(arr1, 0, n1 - 1);
return 0;
}
Java
// Java implementation of find fixed
// index using binary search
class GFG
{
// Main Function to find fixed
// index using binary search
static int binarySearch(int arr[], int low,
int high)
{
if (high < low)
return -1;
// low + (high - low) / 2
int mid = (low + high) / 2;
int midValue = arr[mid];
if (mid == arr[mid])
return mid;
// Search left
int leftindex = Math.min(mid - 1, midValue);
int left = binarySearch(arr, low, leftindex);
if (left >= 0)
return left;
// Search right
int rightindex = Math.max(mid + 1, midValue);
int right = binarySearch(arr, rightindex, high);
return right;
}
// Driver code
public static void main(String[] args)
{
// input 1
int arr[] = {-10, -5, 2, 2, 2,
3, 4, 7, 9, 12, 13};
System.out.println("Fixed Point is " +
binarySearch(arr, 0, arr.length - 1));
// input 2
int arr1[] = {-10, -1, 3, 3, 10,
30, 30, 50, 100};
System.out.println("Fixed Point is " +
binarySearch(arr1, 0, arr1.length - 1));
}
}
Python3
# Python 3 implementation to find fixed
# index using binary search
# Main Function to find fixed
# index using binary search
def binarySearch(arr, low, high):
if (high < low):
return -1
# low + (high - low) / 2
mid = int((low + high) / 2)
midValue = arr[mid]
if (mid == arr[mid]):
return mid
# Search left
leftindex = min(mid - 1, midValue)
left = binarySearch(arr, low, leftindex)
if (left >= 0):
return left
# Search right
rightindex = max(mid + 1, midValue)
right = binarySearch(arr, rightindex, high)
return right
# Driver code
if __name__ == '__main__':
# input 1
arr = [-10, -5, 2, 2, 2, 3,
4, 7, 9, 12, 13]
n = len(arr)
print("Fixed Point is",
binarySearch(arr, 0, n - 1))
# input 2
arr1 = [-10, -1, 3, 3, 10,
30, 30, 50, 100]
n1 = len(arr)
print("Fixed Point is",
binarySearch(arr1, 0, n1 - 1))
# This code is contributed by
# Shashank_Sharma
C#
// C# implementation of find fixed
// index using binary search
using System;
class GFG
{
// Main Function to find fixed
// index using binary search
static int binarySearch(int []arr, int low,
int high)
{
if (high < low)
return -1;
// low + (high - low) / 2
int mid = (low + high) / 2;
int midValue = arr[mid];
if (mid == arr[mid])
return mid;
// Search left
int leftindex = Math.Min(mid - 1, midValue);
int left = binarySearch(arr, low, leftindex);
if (left >= 0)
return left;
// Search right
int rightindex = Math.Max(mid + 1, midValue);
int right = binarySearch(arr, rightindex, high);
return right;
}
// Driver Code
public static void Main()
{
// input 1
int []arr = {-10, -5, 2, 2, 2,
3, 4, 7, 9, 12, 13};
Console.WriteLine("Fixed Point is " +
binarySearch(arr, 0, arr.Length - 1));
// input 2
int []arr1 = {-10, -1, 3, 3, 10,
30, 30, 50, 100};
Console.Write("Fixed Point is " +
binarySearch(arr1, 0, arr1.Length - 1));
}
}
// This code is contributed by nitin mittal.
PHP
<?php
// PHP implementation to
// find fixed index using
// binary search
// Main Function to find fixed
// index using binary search
function binarySearch($arr,
$low,
$high)
{
if ($high < $low)
return -1;
// low + (high - low) / 2
$mid = floor(($low + $high) / 2);
$midValue = $arr[$mid];
if ($mid == $arr[$mid])
return $mid;
// Search left
$leftindex = min($mid - 1,
$midValue);
$left = binarySearch($arr, $low,
$leftindex);
if ($left >= 0)
return $left;
// Search right
$rightindex = max($mid + 1,
$midValue);
$right = binarySearch($arr,
$rightindex,
$high);
return $right;
}
// Driver code
// input 1
$arr = array(-10, -5, 2, 2, 2, 3,
4, 7, 9, 12, 13);
$n = sizeof($arr) / sizeof($arr[0]);
echo "Fixed Point is ",
binarySearch($arr, 0, $n - 1);
// input 2
$arr1 = array(-10, -1, 3, 3, 10,
30, 30, 50, 100);
$n1 = sizeof($arr) / sizeof($arr1[0]);
echo "\nFixed Point is ",
binarySearch($arr1, 0, $n1 - 1);
// This code is contributed by nitin mittal.
?>
Javascript
<script>
// Javascript implementation to find fixed
// index using binary search
// Main Function to find fixed
// index using binary search
function binarySearch(arr, low, high)
{
if (high < low)
return -1;
// low + (high - low) / 2
var mid = parseInt((low + high) / 2);
var midValue = arr[mid];
if (mid == arr[mid])
return mid;
// Search left
var leftindex = Math.min(mid - 1, midValue);
var left = binarySearch(arr, low, leftindex);
if (left >= 0)
return left;
// Search right
var rightindex = Math.max(mid + 1, midValue);
var right = binarySearch(arr, rightindex, high);
return right;
}
// Driver code
// input 1
var arr = [-10, -5, 2, 2, 2,
3, 4, 7, 9, 12, 13];
var n = arr.length;
document.write("Fixed Point is "
+ binarySearch(arr, 0, n - 1));
// input 2
var arr1 = [-10, -1, 3, 3, 10,
30, 30, 50, 100];
var n1 = arr1.length;
document.write("<br>Fixed Point is "
+ binarySearch(arr1, 0, n1 - 1));
// This code is contributed by rrrtnx.
</script>
Fixed Point is 2 Fixed Point is 3
Paradigma algorítmico: Divide y vencerás
Complejidad de tiempo: O(Logn)
Espacio auxiliar: O(1)
Este artículo es una contribución del Sr. Somesh Awasthi . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
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