[알고리즘][JS] 검색 알고리즘이란?

 

검색 알고리즘

많은 사람들이 구글을 떠올릴것입니다.
구글이 사용하는 알고리즘은 매우 까다롭고 세상에서 가장 어려운 알고리즘중 하나일것입니다.
많은 부분이 계속해서 변경됩니다. 개인정보 사용기록 등등..
클릭한 것들에 따라 알고리즘이 엄청나게 변화한다는것은 알고 있을것 입니다.
제가 강아지를 검색한 결과와 다른사람이 검색한 결과는 다를 것인것 처럼요.

문자열이 있는데 해당 문자열에 포함 된 다른 문자열이있는지 확인을하는경우를 예로들수있습니다.
혹은 다른사람들이 회원가입을 하는 경우라던가. 사용자명이 사용중인지 알려줘야 하기 때문입니다.

배열에 대한 검색

미국의 주가 포함된 배열이 있다고 가정하겠습니다.

const usStates = [
  "Alabama", "Alaska", "Arizona", "Arkansas", "California", "Colorado", "Connecticut",
  "Delaware", "Florida", "Georgia", "Hawaii", "Idaho", "Illinois", "Indiana", "Iowa",
  "Kansas", "Kentucky", "Louisiana", "Maine", "Maryland", "Massachusetts", "Michigan",
  "Minnesota", "Mississippi", "Missouri", "Montana", "Nebraska", "Nevada", "New Hampshire",
  "New Jersey", "New Mexico", "New York", "North Carolina", "North Dakota", "Ohio", "Oklahoma",
  "Oregon", "Pennsylvania", "Rhode Island", "South Carolina", "South Dakota", "Tennessee",
  "Texas", "Utah", "Vermont", "Virginia", "Washington", "West Virginia", "Wisconsin", "Wyoming"
];

누군가가 회원가입을 하려합니다. 미국의 주를 입력 혹은 선택 했을때, 그 값이 배열에 존재하는지
확인하는 방법은 어떤것이 있는지 찾는법 중 하나는, 모든 개별항목을 순서대로 탐색하는 것 일것 입니다.

만약 Texas 라면 0번부터 쭉 배열을 이동하며 Texas를 찾을것 입니다.
usStates.indexOf('Texas') 이런식으로. 반복문을 사용하여 찾을 것 같습니다.
이것을 선형 검색이라고 하며 자바스크립트에서는 자체적으로 선형 검색을 지원합니다.

• indexOf
• includes
• find
• findIndex

하지만, 엄청나게 큰 사이트에서 회원가입 아이디 중복값을 찾는다 가정하였을때 몇백만 몇천만개의 아이디의 중복을 찾아내는 알고리즘에
무작정 선형 검색을 사용할 수는 없을 것입니다.

선형검색의 시간복잡도

선형검색의 시간복잡도는
최선의 경우 O(1)이며 최악의 경우 O(n) 입니다.
평균적으로 O(n)의 시간복잡도를 가지고 있습니다.

선형검색이 하나씩 하나씩 확인했다면,
이진검색은 한번의 검색시에 남은항목의 절반을 없애며 값을 찾아갑니다.
이진검색을 사용할 때에 주의사항은, 이진검색은 분류된 배열을 대상으로만 작동하므로, 데이터가 분류 되어 있어야 합니다.
숫자를 가장 작은수 -> 가장 큰수나 큰수 -> 낮은수로 정렬 한뒤 사용해야 합니다.

똑같이 미국 주 목록에서 Texas 를 찾아간다고 하겠습니다.
이진검색의 탐색 과정은 다음과 같습니다.
정렬된 배열을 준비합니다.
검색할 값(target)을 지정합니다.
배열의 중간 요소(mid)를 선택합니다.
중간 요소와 찾고자 하는 값(target)을 비교합니다.
만약 중간 요소가 찾고자 하는 값과 동일하다면 검색 성공으로 처리하고 종료합니다.
만약 중간 요소가 찾고자 하는 값보다 작다면, 배열의 오른쪽 반을 대상으로 이진 검색을 재귀적으로 수행합니다.
만약 중간 요소가 찾고자 하는 값보다 크다면, 배열의 왼쪽 반을 대상으로 이진 검색을 재귀적으로 수행합니다.
찾을 때까지 반복합니다.

이러한 과정을 분할과 정복이라고 합니다.

이진검색의 시간복잡도

이진검색의 최선의 시간복잡도는 O(1)이며 최악과 평균적 시간복잡도는 O(log n) 입니다.
최선 시간 복잡도 (Best Case): O(1)
최악 시간 복잡도 (Worst Case): O(log n)
평균 시간 복잡도 (Average Case): O(log n)