많은 문제들은 어느 정도 뻔하기 때문에(?) 문제를 많이 풀다보면 문제를 봤을 때 어떤 알고리즘을 써야겠다는 느낌이 오긴 하지만, 일단 두 알고리즘의 특성을 아는 게 중요하겠네요. 특성을 이미 알고 계시다면, 문제에 따라 메리트(?)가 있는 쪽을 쓰면 됩니다.

선형 탐색은 너무 뻔해서 이분 탐색을 설명하자면, 이분 탐색은 수행하는 시간이 입력의 크기가 꽤 커도 그렇게 오래 걸리지 않는다는 특징이 있습니다. 식으로 말하자면 시간복잡도가 O(log n)입니다. 다만, 탐색을 하려는 목록이 정렬이 되어 있어야 사용할 수 있습니다. 이번 문제는 탐색을 하려는 목록 A가 고정이기 때문에 한 번만 정렬해두면 선형 탐색보다 빠르게 수행이 되는 이분 탐색을 할 수 있기 때문에, 이분 탐색을 하는 겁니다. 만약에 이번 문제가 M이 언제나 1이었다 하면 이분 탐색을 못 하는 건 아니지만 하기 전에 먼저 정렬을 해야 하기 때문에 선형 탐색에 비해 메리트가 없습니다.

그리고 문제 제한을 볼 때 선형 탐색이 안 될 것 같다는 추측은 할 수 있습니다. 이 바닥(?)에 전해지는 법칙으로 "1초에 1억번 내지 10억번 연산까지 가능"이라는 법칙이 있습니다. 정확한 건 아니고 느낌이 그렇다고 생각해주시면 됩니다. 이 문제에서 최대의 입력이 들어오면 10만개의 수에 대해서 길이 10만 배열에 대해 선형 탐색을 하면 100억번 쯤의 연산이 필요하기 때문에 아마 시간초과가 될 거라고 추측할 수 있습니다.