Pagini recente » Cod sursa (job #3296756) | Istoria paginii runda/sacou/clasament | Cod sursa (job #2404272) | Cod sursa (job #1934316) | Cod sursa (job #1677126)
#include <iostream>
#include <fstream>
#include <vector>
std::ifstream in("cautbin.in");
std::ofstream out("cautbin.out");
int CautaBinar(int vec[], int &elem, int low, int high)
{
// conditia de oprire
if(low > high)
{
return -1;
}
int mid = low + (low + high) / 2;
if(vec[mid] == elem)
{
return mid;
}
if(vec[mid] > elem)
{
return CautaBinar(vec, elem, low, mid - 1);
}
else
{
return CautaBinar(vec, elem, mid + 1, high);
}
}
int CautaBinar1(int vec[], int &elem, int low, int high)
{
// conditia de oprire
if(low > high)
{
return -1;
}
int mid = low + (low + high) / 2;
if(vec[mid] == elem)
{
return mid;
}
if(vec[mid] > elem && vec[mid - 1] < elem)
{
return mid - 1;
}
if(vec[mid] > elem)
{
return CautaBinar1(vec, elem, low, mid - 1);
}
else
{
return CautaBinar1(vec, elem, mid + 1, high);
}
}
int CautaBinar2(int vec[], int &elem, int low, int high)
{
if(low > high)
{
return -1;
}
int mid = low + (low + high) / 2;
if(vec[mid] == elem)
{
return mid;
}
if(vec[mid] < elem && vec[mid + 1] > elem)
{
return mid + 1;
}
if(vec[mid] > elem)
{
return CautaBinar1(vec, elem, low, mid - 1);
}
else
{
return CautaBinar1(vec, elem, mid + 1, high);
}
}
void getRequests(int vec[], std::pair<int , int> &p, int &dimVec)
{
int poz;
if(p.first == 0)
{
poz = CautaBinar(vec, p.second, 0, dimVec - 1);
if(poz == -1)
{
out << -1 << "\n";
return;
}
std::cout << "Pozitia este : " << poz << "\n";
int k = poz;
while(vec[k + 1] == vec[poz])
{
++k;
}
// in output vectorul este contorizat de la 1 la n
out << k + 1 << "\n";
}
else if(p.first == 1)
{
poz = CautaBinar1(vec, p.second, 0, dimVec - 1);
std::cout << "Pozitia este : " << poz << "\n";
int k = poz;
if(vec[poz] == p.second)
{
while(vec[k + 1] == vec[poz])
{
++k;
}
out << k + 1 << "\n";
}
else
{
while(vec[k - 1] == vec[poz])
{
--k;
}
--k;
out << k + 1 << "\n";
}
}
else
{
std::cout << p.first << "\n";
poz = CautaBinar2(vec, p.second, 0, dimVec - 1);
std::cout << "Pozitia este : " << poz << "\n";
int k = poz;
if(vec[poz] == p.second)
{
while(vec[k - 1] == vec[poz])
{
--k;
}
out << k + 1 << "\n";
}
else
{
while(vec[k - 1] != vec[poz])
{
--k;
}
--k;
out << k + 1 << "\n";
}
}
}
int main(void)
{
int dimVec;
in >> dimVec;
int vec[dimVec];
for(int i = 0; i < dimVec; i++)
{
in >> vec[i];
}
int requests;
in >> requests;
// first -> tipul cererii
// second -> numarul pe cerere
std::vector < std::pair <int, int> > v;
int type;
int number;
for(int i = 0; i < requests; i++)
{
in >> type;
in >> number;
std::pair <int, int> p(type, number);
v.push_back(p);
}
for(int i = 0; i < requests; i++)
{
getRequests(vec, v[i], dimVec);
}
}