Дан массив из n элементов и дается число k написать программу которая находит элемент...

+669 голосов
4.3m просмотров

Дан массив из n элементов и дается число k написать программу которая находит элемент массива равный k и выводит его индекс или -1 если такого элемента нет ВАЖНО: програма должна работать быстрее чем за линейное время то есть просто перебор не пройдет


Информатика | 4.3m просмотров
Дано ответов: 2
+81 голосов

Ответ:

#include

#include

using namespace std;

 

int main()

{

   SetConsoleCP(1251);

   SetConsoleOutputCP(1251);

   int n;

   cin >> n;//Вводим размер массива

   int *arr = new int[n];

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

   {

       cin >> arr[i];//Вводим числа массива

   }

   int k;

   cin >> k;//Вводим искомое

   int index = 0;

 

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

   {

       if (arr[i] == k)

       {

           index = i;//Запоминаем индекс числа в массиве

           break;//Так как цифры во входных данных две - прерываем цикл при первом же совпадении

       }

   }

   cout << index-1 << endl;</p>

   system("pause");

   return 0;

}

(1.2k баллов)
+138

спасибо manarchi

+140 голосов

#include

using namespace std;

int main() {

   int n,k;

   cin >> n;

   pair a[n];

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

       int x;

       cin >> x;

       a[i] = {x,i};

   }

   cin >> k;

   sort(a,a+n);

   int l = 0, r = n-1;

   while(l <= r){</strong>

       int mid = (l+r)/2;

       if(a[mid].first == k){

           cout << a[mid].second;</strong>

           return 0;

       }

       else if(a[mid].first < k)

           l = mid+1;

       else if(a[mid].first > k)

           r = mid-1;

   }

   cout << -1;</strong>

}

(152k баллов)
+69

спасибо