Учитывая массив из n различных целых чисел, отсортированных в порядке возрастания, напишите функцию, которая возвращает фиксированную точку в массиве, если в массиве присутствует какая-либо фиксированная точка, иначе возвращается -1. Фиксированная точка в массиве — это такой индекс i, что arr [i] равен i. Обратите внимание, что целые числа в массиве могут быть отрицательными.
Примеры:
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
Метод 1 (линейный поиск)
Линейно ищите индекс i такой, что arr [i] == i. Верните первый найденный такой индекс. Спасибо вечера за предложение этого решения.
C ++
#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;
}
return -1;
}
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;
}
|
С
#include<stdio.h>
int linearSearch(int arr[], int n)
{
int i;
for(i = 0; i < n; i++)
{
if(arr[i] == i)
return i;
}
return -1;
}
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;
}
|
Джава
class Main
{
static int linearSearch(int arr[], int n)
{
int i;
for(i = 0; i < n; i++)
{
if(arr[i] == i)
return i;
}
return -1;
}
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));
}
}
|
питон
def linearSearch(arr, n):
for i in range(n):
if arr[i] is i:
return i
return -1
arr = [-10, -1, 0, 3, 10, 11, 30, 50, 100]
n = len(arr)
print("Fixed Point is " + str(linearSearch(arr,n)))
|
C #
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;
}
return -1;
}
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));
}
}
|
PHP
<?php
function linearSearch($arr, $n)
{
for($i = 0; $i < $n; $i++)
{
if($arr[$i] == $i)
return $i;
}
return -1;
}
$arr = array(-10, -1, 0, 3, 10,
11, 30, 50, 100);
$n = count($arr);
echo "Fixed Point is ".
linearSearch($arr,$n);
?>
|
Выход:
Fixed Point is 3
Сложность времени: O (n)
Метод 2 (бинарный поиск)
Сначала проверьте, является ли средний элемент Фиксированной Точкой или нет. Если это так, верните его; в противном случае проверьте, больше ли индекс среднего элемента, чем значение индекса. Если индекс больше, то Фиксированная точка (точки) находится справа от средней точки (очевидно, только если есть Фиксированная точка). В противном случае фиксированные точки находятся на левой стороне.
C ++
#include <bits/stdc++.h>
using namespace std;
int binarySearch(int arr[], int low, int high)
{
if(high >= low)
{
int mid = (low + high)/2;
if(mid == arr[mid])
return mid;
if(mid > arr[mid])
return binarySearch(arr, (mid + 1), high);
else
return binarySearch(arr, low, (mid -1));
}
return -1;
}
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;
}
|
С
#include<stdio.h>
int binarySearch(int arr[], int low, int high)
{
if(high >= low)
{
int mid = (low + high)/2;
if(mid == arr[mid])
return mid;
if(mid > arr[mid])
return binarySearch(arr, (mid + 1), high);
else
return binarySearch(arr, low, (mid -1));
}
return -1;
}
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;
}
|
Джава
class Main
{
static int binarySearch(int arr[], int low, int high)
{
if(high >= low)
{
int mid = (low + high)/2;
if(mid == arr[mid])
return mid;
if(mid > arr[mid])
return binarySearch(arr, (mid + 1), high);
else
return binarySearch(arr, low, (mid -1));
}
return -1;
}
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));
}
}
|
питон
def binarySearch(arr, low, high):
if high >= low:
mid = (low + high)//2
if mid is arr[mid]:
return mid
if mid > arr[mid]:
return binarySearch(arr, (mid + 1), high)
else:
return binarySearch(arr, low, (mid -1))
return -1
arr = [-10, -1, 0, 3, 10, 11, 30, 50, 100]
n = len(arr)
print("Fixed Point is " + str(binarySearch(arr, 0, n-1)))
|
C #
using System;
class GFG
{
static int binarySearch(int []arr, int low, int high)
{
if(high >= low)
{
int mid = (low + high)/2;
if(mid == arr[mid])
return mid;
if(mid > arr[mid])
return binarySearch(arr, (mid + 1), high);
else
return binarySearch(arr, low, (mid -1));
}
return -1;
}
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
function binarySearch($arr, $low, $high)
{
if($high >= $low)
{
$mid = (int)(($low + $high) / 2);
if($mid == $arr[$mid])
return $mid;
if($mid > $arr[$mid])
return binarySearch($arr, ($mid + 1), $high);
else
return binarySearch($arr, $low, ($mid - 1));
}
return -1;
}
$arr = array(-10, -1, 0, 3, 10,
11, 30, 50, 100);
$n = count($arr);
echo "Fixed Point is: "
. binarySearch($arr, 0, $n - 1);
?>
|
Выход:
Fixed Point is 3
Алгоритмическая парадигма: разделяй и властвуй
Сложность времени: O (Logn)
Найти фиксированную точку (значение, равное индексу) в данном массиве | Дубликаты разрешены
Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.
Рекомендуемые посты:
Найти фиксированную точку (значение, равное индексу) в данном массиве
0.00 (0%) 0 votes