JavaScript 배열 탐색 알고리즘 질문드립니다.

안녕하세요! 먼저 질문자님께서도 아시다시피, 이진탐색은 정렬된 리스트에 한해 O(logN)의 시간 복잡도를 가지고, 선형탐색은 정렬 여부에 상관없이 O(N)의 시간 복잡도를 가집니다. JavaScript sort 내장 함수는 구글 V8엔진을 기준으로 Timsort라는 정렬 알고리즘을 사용하는데, O(NlogN)의 시간 복잡도를 가집니다. 말씀하신 기수정렬을 한다고 해도 O(dN)의 시간 복잡도를 가지겠죠. 그럼 정렬되지 않은 리스트에서 정렬 후 이진탐색을 한다고 했을 때, 총 O(NlogN) + O(logN) 또는 O(dN) + O(logN)의 시간 복잡도를 가질 것 입니다. 이는 선형탐색의 시간 복잡도 O(N)과 비교했을 때, 더 안 좋은 수치입니다. 따라서 정렬되지 않은 리스트의 경우에는 선형탐색이 이진탐색보다 언제나 빠를 것 같군요. (어떤 정렬 알고리즘의 시간 복잡도도 최소 O(N)이상이므로) 추가로 실무 Frontend를 기준으로 말씀드리면, 개인적으로 아직까지 이진탐색을 사용해야했던 경험은 없긴 합니다. 왜냐하면 Frontend에서 어떤 조건에 맞는 데이터가 필요하다면 Backend API 요청을 통해 받는 것이 일반적이며, 이미 Frontend에서 가지고 있는 데이터에서 탐색을 한다고 해도 탐색할 조건이 이미 정렬되어있지 않은 경우가 많고, 정렬이 되어있어도 특정 값 하나만을 탐색하는 경우는 드물기 때문입니다. 물론 여러 값을 모두 이진탐색을 통해서 탐색할 수 있으나, 이것도 무조건 효율적이지는 않습니다. 예컨대 100,000개의 데이터에서 약 1,000개 미만의 데이터를 탐색하는 경우 이진탐색을 여러 번 사용하는 것(O(k * logN))이 JavaScript 내장 함수 filter(O(N))를 사용하는 것보다 아주 미세하게 빨랐으나, 100,000개 중 약 1,000개 이상의 데이터를 탐색하는 경우 이진탐색이 좀 더 느린 결과를 냈습니다. (filter는 평균 10ms 내외, 이진탐색은 찾으려는 데이터 수에 따라 1~50ms) 정리하자면 아래와 같은 이유로, 실무 Frontend에서는 이진탐색을 거의 사용하지 않을 것 같습니다. 1. 기본적으로 데이터 탐색은 Backend API 요청을 통해서 받는다. (100,000개의 데이터를 한 번에 가져와서 Frontend에서 탐색을 하는 상황을 생각해보면 데이터 최초 요청 시 네트워크 부하가 매우 클 것입니다. 그래서 보통은 페이지네이션 기술을 통해 특정 개수단위로 데이터를 받습니다.) 2. 100,000개의 데이터를 어쨌든 받았다고 치고, Frontend에서 가지고 있는 데이터에서 탐색을 한다고 해도 정렬되지 않은 데이터일 확률이 크다. (예컨대 노래 데이터에서 제목, 가수, 앨범 이름별 탐색을 할 수 있어야 한다고 하면, 3개 조건 모두에 맞게 데이터가 정렬되어있을 수는 없으니까요) 3. 정렬된 데이터라고 해도 여러 값을 탐색하는 경우 이진탐색이 무조건 효율적이지는 않다. (1개의 값 혹은 소량의 값만 탐색하는 경우 이진탐색의 효율이 조금 더 좋겠으나, JavaScript 내장 함수 filter를 사용하고도 모든 경우에 충분히 빠른 성능을 낼 수 있으며, 가독성 측면에서도 훨씬 뛰어나기 때문입니다.)