Рубрики

Найти фиксированную точку (значение, равное индексу) в данном массиве

Учитывая массив из 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 ++

// 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; 

    

  

    / * Если фиксированная точка отсутствует, вернуть -1 * /

    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; 

  
// Это код, предоставленный rathbhupendra

С

// C программа для проверки фиксированной точки
// в массиве с использованием линейного поиска
#include<stdio.h>

  

int linearSearch(int arr[], int n)

{

    int i;

    for(i = 0; i < n; i++)

    {

        if(arr[i] == i)

            return i;

    }

  

    / * Если фиксированная точка отсутствует, вернуть -1 * /

    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;

}

Джава

// Java-программа для проверки фиксированной точки
// в массиве с использованием линейного поиска

   

class Main

{

    static int linearSearch(int arr[], int n)

    {

        int i;

        for(i = 0; i < n; i++)

        {

            if(arr[i] == i)

                return i;

        }

        

        / * Если нет фиксированной точки

           затем верните -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 " 

                     + linearSearch(arr, n));

    }

}

питон

# Программа Python для проверки фиксированной точки
# в массиве с использованием линейного поиска

def linearSearch(arr, n):

    for i in range(n):

        if arr[i] is i:

            return i

    # Если фиксированная точка отсутствует, вернуть -1

    return -1

  
# Драйвер программы для проверки вышеуказанных функций

arr = [-10, -1, 0, 3, 10, 11, 30, 50, 100]

n = len(arr)

print("Fixed Point is " + str(linearSearch(arr,n)))

  
# Этот код предоставлен Pratik Chhajer

C #

// 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;

        }

          

        / * Если нет фиксированной точки

        затем верните -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 "+ linearSearch(arr, n));

    }

}

  
// Этот код предоставлен Sam007

PHP

<?php
// PHP программа для проверки фиксированной точки
// в массиве с использованием линейного поиска

  

function linearSearch($arr, $n)

{

    for($i = 0; $i < $n; $i++)

    {

        if($arr[$i] == $i)

            return $i;

    }

  

    // Если нет фиксированной точки, то

    // возвращаем -1

    return -1;

}

  

    // Код драйвера

    $arr = array(-10, -1, 0, 3, 10, 

                  11, 30, 50, 100);

    $n = count($arr);

    echo "Fixed Point is ".

            linearSearch($arr,$n);

  
// Этот код предоставлен Sam007
?>


Выход:

Fixed Point is 3

Сложность времени: O (n)

Метод 2 (бинарный поиск)
Сначала проверьте, является ли средний элемент Фиксированной Точкой или нет. Если это так, верните его; в противном случае проверьте, больше ли индекс среднего элемента, чем значение индекса. Если индекс больше, то Фиксированная точка (точки) находится справа от средней точки (очевидно, только если есть Фиксированная точка). В противном случае фиксированные точки находятся на левой стороне.

C ++

// C ++ программа для проверки фиксированной точки
// в массиве с использованием бинарного поиска
#include <bits/stdc++.h>

using namespace std;

  

int binarySearch(int arr[], int low, int high) 

    if(high >= low) 

    

        int mid = (low + high)/2; / * низкий + (высокий - низкий) / 2; * /

        if(mid == arr[mid]) 

            return mid; 

        if(mid > arr[mid]) 

            return binarySearch(arr, (mid + 1), high); 

        else

            return binarySearch(arr, low, (mid -1)); 

    

  

    / * Вернуть -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; 

  
// Этот код предоставлен rathbhupendra

С

// C программа для проверки фиксированной точки
// в массиве с использованием бинарного поиска
#include<stdio.h>

  

int binarySearch(int arr[], int low, int high)

{

    if(high >= low)

    {

        int mid = (low + high)/2;  / * низкий + (высокий - низкий) / 2; * /

        if(mid == arr[mid])

            return mid;

        if(mid > arr[mid])

            return binarySearch(arr, (mid + 1), high);

        else

            return binarySearch(arr, low, (mid -1));

    }

  

    / * Вернуть -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;

}

Джава

// Java-программа для проверки фиксированной точки
// в массиве с использованием бинарного поиска

  

class Main

{

    static int binarySearch(int arr[], int low, int high)

    {

        if(high >= low)

        {   

            / * низкий + (высокий - низкий) / 2; * /

            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));

        }

        

        / * Вернуть -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));        

    

}

питон

# Программа Python для проверки фиксированной точки
# в массиве с использованием бинарного поиска

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))

      

    # Вернуть -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)))

  

  
# Этот код предоставлен Pratik Chhajer

C #

// C # программа для проверки фиксированной точки
// в массиве с использованием бинарного поиска

using System;

  

class GFG

{

    static int binarySearch(int []arr, int low, int high)

    {

        if(high >= low)

        

            // низкий + (высокий - низкий) / 2;

            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));

        }

          

        / * Вернуть -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));     

    

}
// Этот код предоставлен Sam007

PHP

<?php
// PHP программа для проверки фиксированного ро
// в массиве с использованием бинарного поиска

  

function binarySearch($arr, $low, $high)

{

    if($high >= $low)

    {

          

         / * низкий + (высокий - низкий) / 2; * /

        $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));

    }

  

    / * Вернуть -1, если есть

       нет фиксированной Po * /

    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);

          
// Этот код предоставлен Anuj_67
?>


Выход:

Fixed Point is 3

Алгоритмическая парадигма: разделяй и властвуй
Сложность времени: O (Logn)

Найти фиксированную точку (значение, равное индексу) в данном массиве | Дубликаты разрешены

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Найти фиксированную точку (значение, равное индексу) в данном массиве

0.00 (0%) 0 votes