검색 알고리즘

📌 검색 알고리즘

배열이나 문자열이 주어질 때, 특정 값이 있는지 확인하는 방법.

크게 선형 검색과 이진 검색이 있다.

1. 선형 검색(Linear Search)

모든 개별 항목을 순서대로 살펴보는 방법

• 시간 복잡도 : O(1) 혹은 O(n)

• 메서드 : indexOf, includes, find, findIndex
  indexOf는 특정 값의 index를 return 한다. (없으면 -1을 return)
  includes는 특정 값의 유무(T/F)를 retun 한다.

예제

Write a function called linearSearch which accepts an array and a value, and returns the index at which the value exists. If the value does not exist in the array, return -1.
Don't use indexOf to implement this function!

반복문을 통해 배열에 있는 요소를 n과 하나씩 비교한다.
(indexOf, includes 같은 메서드들의 알고리즘도 이와 같다.)

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

2. 이진 검색(Binary Search)

정렬된 배열의 중간 지점부터 왼쪽이나 오른쪽으로 검색하는 방법

• 분할 정복 패턴을 이용한다.
• 선형 검색보다 훨씬 빠르다.
• 시간 복잡도 : O(1) 혹은 O(log n)

⚠️ 주의 사항

: 이진 검색은 정렬된 배열에서만 작동하므로 데이터가 반드시 정렬되어 있어야 한다.
(정렬되지 않았을 때는 쓸모가 없기 때문에 선형 검색을 활용한다.)

예시

ex) [1,3,8,13,18,21,25,27,30,32] 에서 25의 위치 찾기

1. 배열의 중간 지점을 찾는다. -> 18
2. 찾아야 하는 값이 중간 지점보다 작으면 왼쪽, 크면 오른쪽으로 검색한다.
3. 18 < 25이므로 18의 오른쪽에 있는 값 [21,25,27,30,32] 에서 다시 중간 지점을 찾는다. -> 27
4. 25 < 27 이므로 27의 왼쪽인 [21,25] 에서 검색하면 25를 찾을 수 있다.

방법

1. 정렬된 배열을 입력받는다.
2. 배열의 시작점에 왼쪽 포인터, 배열의 마지막 지점에 오른쪽 포인터를 하나 만들어준다.
   (왼쪽 포인터 : 0, 오른쪽 포인터 : 배열 길이 - 1)
3. 중간 지점 선택 : 좌측 포인터와 우측 포인터의 평균을 중간점으로 설정한다.
   (평균이 소수점이 나올 수도 있으므로 Math.floor/Math.ceil 해주기)
4. 조건 설정 : 항목을 찾지 못했고, 좌측 포인터가 우측 포인터보다 작거나 같을 때에는 연산을 계속한다.
5. 연산하기
   값이 중간 지점보다 크면 좌측 포인터를 중간 index로 설정.
   값이 중간 지점보다 작으면 우측 포인터를 중간 index로 설정.
6. 결과
   값을 찾으면 index를 return.
   연산이 끝난 후에도 값을 찾기 못하면 -1을 return.

예제

1. 시작 지점과 끝 지점에 포인터를 각각 둔다.
2. 반복문을 이용해 중간 지점과 주어진 숫자가 같지 않고, 시작 포인터가 끝 포인터보다 커지지 않을 때까지만 연산을 해준다.
3. 주어진 숫자와 중간 지점의 값을 비교하며 포인터를 이동시키고, 중간 지점을 업데이트 한다.
   ⭐️ 중요 : 중간 지점은 이미 체크되었기 때문에 포인터를 이동할 때 중간 지점은 제외해준다.(-1이나 +1로)
   (중간 지점이 나누어 떨어지지 않고 소수점이 나오는 경우가 있을 수 있기 때문에 Math.floor를 해주어야 한다.)
4. 일치하는 값을 찾으면 index를 return하고, 일치하는 값을 찾지 못했다면 -1을 return한다.

function binarySearch(arr, elem) {
    var start = 0;
    var end = arr.length - 1;
    var middle = Math.floor((start + end) / 2);
    while(arr[middle] !== elem && start <= end) {
        if(elem < arr[middle]) end = middle - 1;
        else start = middle + 1;
        middle = Math.floor((start + end) / 2);
    }
    return arr[middle] === elem ? middle : -1;
}

binarySearch([2,5,6,9,13,15,28,30], 103)
// binarySearch([1,2,3,4,5],2) // 1
// binarySearch([1,2,3,4,5],3) // 2

3. Naive String Search

긴 문자열에서 부분 문자열을 검색하는 것과 관련됨.

예제

긴 문자열에서 짧은 문자열의 갯수 찾기

1. 중첩된 반복문을 이용해 긴 문자열에 있는 문자들과 짧은 문자열에 있는 문자들을 비교한다.
2. 문자가 하나라도 일치하지 않으면 반복문을 빠져나오고, 문자가 전부 일치하면 count를 증가시킨다.
   (짧은 문자열을 다 검색할 때까지 반복문이 실행되어 j가 짧은 문자열의 마지막 index까지 왔다면 전부 일치한다는 뜻이 된다.)

function naiveSearch(long, short){
    var count = 0;
    for(var i = 0; i < long.length; i++){
        for(var j = 0; j < short.length; j++){
           if(short[j] !== long[i+j]) break;
           if(j === short.length - 1) count++;
        }
    }
    return count;
}

naiveSearch("lorie loled", "lol") // 1

ex) naiveSearch("lorie loled", "lol")

i	j
l   l
o   o
l   r    break
o   l    break
r   l    break
i   l    break
e   l    break
l   l    
o   o
l   l    count++
o   l    break
l   l
e   o    break
d   l    break