uva 1237 - Expert Enough? Solution

Algorithm  : Binary Search

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <stdio.h>


using namespace std;

class Car{
public:
string name;
long low_cost;
long high_cost;
};

bool car_sort_with_low_cost(Car *c1, Car *c2){
if (c1->low_cost < c2->low_cost)
return true;
return false;
}

vector<Car*> vec;

void car_binary_search(int start, int end, int val, int &index){
if (start == end){
index = start;
return;
}

int mid = (start + end) / 2;

int val1 = vec[mid]->low_cost;
int val2 = vec[mid+1]->low_cost;
if (val > val1 && val <= val2){
index = mid;
return;
}
if (val2 == val){
car_binary_search(mid + 1, end, val, index);
return;
}
if (val1 == val){
index = mid;
return;
}
if (val1>val){
car_binary_search(start, mid,val,index);
return;
}
if (val2 > val){
index = mid + 1;
return;
}
else{
car_binary_search(mid + 1, end, val, index);
return;
}
}

int main(){
freopen("test.txt","r",stdin);
freopen("out.txt", "w", stdout);
int kase, i, m, p, index;
bool flag;
cin >> kase;
while (kase--){
cin >> m;
vec.clear();
while (m--){
Car *c = new Car();
cin >> c->name >> c->low_cost >> c->high_cost;
vec.push_back(c);
}
sort(vec.begin(), vec.end(), car_sort_with_low_cost);
cin >> m;
while(m--){
cin >> p;
car_binary_search(0, vec.size() - 1, p, index);

flag = false;
for (i = index; i >=0; i--){
if (p >= vec[i]->low_cost && p <= vec[i]->high_cost){
if (flag){
flag = false;
break;
}
else{
flag = true;
index = i;
}
}
else if (vec[i]->low_cost > p)
break;
}
if (flag)
cout << vec[index]->name << endl;
else
cout << "UNDETERMINED" << endl;
}
if (kase > 0)
cout << endl;
}
return 0;
}