검색 & 탐색 알고리즘 (Search algorithm)

탐색 알고리즘 (Search algorithm)

• 탐색과 정렬은 알고리즘에서 가장 빈번하게 사용된다.
• 구글과 같은 서비스는 검색 엔진을 가지고 있는데 이러한 검색 엔진에서 탐색 알고리즘이 사용된다.
  
  

 선형 탐색 (Linear Search)

• 첫 부분부터 끝 부분까지 하나씩 확인하는 방식
• JS의 includes, find, findIndex, indexOf와 같은 메서드가 사용하는 알고리즘

 

선형 탐색 의사코드

1. 배열 안에 찾고자 하는 값이 있으면 해당 인덱스를 반환한다.
2. 배열을 전부 순회하였음에도 일치하는 값이 없을 경우 -1을 반환한다.

fuction linerSearch(arr, val) {
    let result = -1;
    for(let i = 0; i < arr.length; i++) {
        if(arr[i] === targetNumber) {
            result = i;
        }
    }
    return result;
}
 
// best case - O(1)
linerSearch([1, 2, 3, 4, 5], 1);
// worst case - O(n)
linerSearch([1, 2, 3, 4, 5], 6);

 

이진 탐색 (Binary Search)

• 배열의 중간 인덱스가 찾고자 하는 값이면 반환하고 그렇지 않은 경우 중간 인덱스의 값과 찾는 값을 비교하여 작거나 큰 경우 배열을 중간값 기준으로 다시 배열을 반토막 내어 중간 인덱스와 찾는 값이 일치할 때까지 연산을 반복하여 일치하는 값이 없으면 -1을 반환하는 코드
• 정렬되어 있는 배열에서만 사용 가능한 검색 방식
• 분할 정복 개념을 가지는 방식

 

이진 탐색 의사 코드

1. 정렬된 배열
2. 좌측 포인터(0), 우측 포인터(last index), 중앙 포인터 선언
3. 항목을 찾았는지? 못 찾았으면 연산 계속
4. 좌측 포인터가 우측 포인터의 위치를 초과하면 종료
5. 중앙 포인터가 찾는 값이면 반환
6. 찾는 값이 중앙 포인터의 값 보다 작으면 좌측 포인터를 중앙 포인터로 이동 
7. 찾는 값이 중앙 포인터의 값 보다 크면 우측 포인터를 중앙 포인터로 이동
8. 연산이 종료되어도 값을 찾지 못하면 -1을 반환한다.

function binarySearch(arr, val){
  let start = 0;
  let end = arr.length - 1;
  let middle = Math.floor((start + end) / 2);
 
  while(arr[middle] !== val && start <= end) {
      if(arr[middle] > val) {
          end = middle - 1;
      } else {
          start = middle + 1;
      }
      middle = Math.floor((start + end) / 2);
  }
 
    return arr[middle] === val ? middle : -1;
}
 
// worst case
console.log(binarySearch([1, 2, 3, 4, 5], 6));

 

업데이트중...