Нахождение местоположения массива
Как видите, я хочу найти расположение данного массива.
Например :
- У меня есть массив {5, 2, 3, 1} (я хочу решить, сколько предположений я хочу угадать)
- Затем программа будет сортировать его {1, 2, 3, 5}
- Наконец, мне дадут шанс угадать число, которое я хотел, сколько угадать (пример: я хочу угадать 2 числа, это 5 и 3. тогда программа будет искать числа 5 и 3. Программа будет скажите мне местоположение в отсортированном массиве. Тогда это «3 найдено в 3, 5 найдено в 4»
Тем не менее, мой код застрял в сортировке
это мой код:
#include <iostream>
using namespace std;
int main(void)
{
int temp, i, j, n, list[100];
cin>>n;
for(i=0; i<n; i++)
{
cin>>list[i];
}
for(i=0; i<n-1; i++)
for(j=i+1; j<n; j++)
if(list[i] > list[j])
{
temp = list[i];
list[i] = list[j];
list[j] = temp;
}
for(i=0; i<n; i++)
cout<<" "<<list[i];
cout<<endl;
return 0;
}
И эта ссылка — полный вопрос моего проекта:
http://uva.onlinejudge.org/external/104/p10474.pdf
Решение
В вашей функции сортировки нет проблем, кстати, вы можете решить исходную проблему в O(nlogn) , твое O(n^2)
код:
#include <iostream>
#include <algorithm>
using namespace std;
int binary_search(int A[], int key, int imin, int imax)
{
if (imax < imin)
return -1;
else
{
int imid = (imax + imin)/2;
if (A[imid] > key)
// key is in lower subset
return binary_search(A, key, imin, imid - 1);
else if (A[imid] < key)
// key is in upper subset
return binary_search(A, key, imid + 1, imax);
else
// key has been found
return imid;
}
}int main() {
// your code goes here
int n,q;
while(1){
cin >> n>> q;
if(n==0)
break;
int* a = new int[n];
int i;
for(i=0;i<n;i++)
cin >> a[i];
sort(a,a+n);
while(q--){
int k;
cin >> k;
k=binary_search(a,k,0,n-1);
if(k==-1)
cout << "not found" << endl;
else
cout << "found at :" << k+1 << endl;
}}
return 0;
}
Другие решения