이분탐색 찾아보시면 도움될듯합니다.

a를 소팅했지만 그 이점을 살리지 못한 방법입니다. 결과적으로 a의 모든 원소를 차례대로 탐색하면서 일치하는 것을 찾기 때문에, 한 개의 수를 탐색하는 데에 평균 n/2개 원소를 탐색해야 하죠.

이 과정을 m번 반복하기 때문에 평균 수행 시간은 정렬 시간은 무시하고 O(mn)으로 볼 수 있습니다. 극한의 입력이 주어지면 mn이 2500억 정도 됩니다. 평균 시간은 1/2이고 가벼운 연산으로만 이루어졌다는 걸 고려해도 절대로 2초 내에 끝낼 수 없습니다.

C, C++ 기준으로, 초당 1억 번의 가벼운 연산을 대략 한계치 정도로 생각하시면 됩니다. 윗분 말씀처럼 이분탐색을 사용하시면 O((n+m)lgn), 극한의 입력에서 약 2천만 정도 되고, 연산도 크게 무겁지 않아서 충분히 해결할 수 있습니다. 조금 다른 방법을 사용해서 O(nlgn + mlgm) 시간에 풀거나, 아예 O(n+m)으로 해결해버리는 방법도 있습니다(상수항이 커서 시간은 크게 개선은 안 됩니다).