[알고리즘] 검색 알고리즘 (자바스크립트)

0. 검색 (Search)

• IndexOf 메서드 같은 배열 인덱싱, 문자열 파싱과 관련된 파트
• 내장함수의 처리 과정을 이해하고, 직접 구현하여 활용할 수 있게 하기 위함

 

1. 선형 검색 (Linear Search)

• 모든 개별 항목을 한 번씩 확인하는 방법
• 첫부분부터 끝부분으로 이동하며 탐색할수도, 역순으로 탐색할수도 있음
• indexOf, includes, find, findIndex 메서드를 통해 선형 검색을 구현

 

기본적인 선형 검색 구현

function linearSearch(arr,value){
  for (var i=0; i<=arr.length;i++){
      if(arr[i]==value)return i
  }
  return -1
}

 

선형 검색의 빅오 연산

• Best 찾고자 하는 값을 곧바로 찾는 경우 : O(1)
• Worst 배열 내의 모든 원소를 돌아 값을 찾는 경우 : O(N)
• 평균적인 연산값을 큰 흐름에서 본다면, O(N)

 

2. 이진 검색 (Binary Search)

• 배열의 중앙부터 탐색, 중앙값을 기준으로 양 영역을 분할하여 찾는 값이 있는 영역만 재탐색
• 반복할 때마다 절반 가량의 연산 분량을 제거할 수 있음
• 정렬된 배열을 대상으로 작동 (ex. 0-9, 9-0, a-z, z-a ..)
• O(log N)의 계산 복잡도를 가짐

 

의사코드

1. 정렬된 배열을 입력으로 받는 함수 작성
2. 배열 양 끝에 위치하는 포인터 Left, Right 생성
3. 루프 정지 조건 설정 - 원하는 값을 찾았는지, 좌측 포인터와 우측 포인터가 역전되었는지
4. 중앙값이 원하는 값보다 작다면, 좌측 포인터를 중앙값으로 변경
5. 중앙값이 원하는 값보다 크다면, 우측 포인터를 중앙값으로 변경
6. 반복하여 원하는 값을 찾은 경우 인덱스를 반환하고, 루프가 끝날 때까지 찾지 못한 경우 -1 반환

 

구현

function binarySearch(arr, value) {
  var start = 0;
  var end = arr.length - 1;
  var middle = Math.floor((start + end) / 2);

  while (arr[middle] !== value) {
    console.log(start, mid, end);

    if (value < arr[middle]) {
      end = middle - 1;
    } else {
      start = middle + 1;
    }
    middle = Math.floor((start + end) / 2);

    if (end < start) return -1;
  }
  console.log(start, mid, end);
  return middle;
}

 

3. 나이브 문자열 검색

• 긴 문자열에서 원하는 문자열을 탐색하는 기본적인 방법. 첫 번째 알파벳부터 탐색하여 일치하면 다음 알파벳을 탐색
• 문자열 끝까지 반복 탐색하여 카운팅
• 이중 루프를 통한 구현