javascript 코딩테스트 - 검색 알고리즘

검색은 말 그대로 간단하다. 

 

어떤 배열안에 해당하는 데이터가 있는지 없는지 확인하기 위한 알고리즘이다.

 

1. 선형 검색 알고리즘 (linear search)

 

검색을 하기 위한 가장 단순한 사고방식의 알고리즘이라고 생각하면 된다.

만약 전체의 집합이 있고 찾고자하는 값이 있다면 전체 집합을 전부 다 살펴보면 된다.

 

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.

linearSearch([10, 15, 20, 25, 30], 15) // 1
linearSearch([9, 8, 7, 6, 5, 4, 3, 2, 1, 0], 4) // 5
linearSearch([100], 100) // 0
linearSearch([1,2,3,4,5], 6) // -1
linearSearch([9, 8, 7, 6, 5, 4, 3, 2, 1, 0], 10) // -1
linearSearch([100], 200) // -1

 

답이 있는지 없는지 true / false로만 선형 검색을 구성할 수 있겠지만 해당하는 인덱스를 출력하도록 해보자.

 

나의 답

function linearSearch(arr,num){
  let idx = 0
  for(let i of arr){
      if(i === num){
          return idx
      }
      idx++
  }
  return -1
}

for...of 구문을 활용하여 반복문을 돌고 해당하는 애를 바로 찾으면 인덱스를 출력하도록 한다. 이미 찾았는데 굳이 뒤의 애들까지 검색할 필요는 없으니 바로 리턴을 했다. 이 알고리즘은 만약 찾고자 하는 값이 여러 개 있다면 그 중 첫번째 값만을 출력한다는 단점(?)을 가지고 있다.

 

이 알고리즘의 복잡도는 어떻게 될까?

베스트 시나리오로는 첫 검색에 바로 찾는 거니깐 O(1)일 것이다. 하지만 최악의 경우라면 맨 마지막까지 다 봐야하므로 O(n)의 복잡도를 가지게 된다. 하지만 없는 경우에도 이 알고리즘은 전체를 다 살펴봐야하기 때문에 아마 O(n)의 복잡도를 훨씬 더 많은 빈도수로 나타낼 것이다. 

 

그럼 이걸 줄일 수 없을까?

 

2. 이진 검색 알고리즘 (binary search)

 

결론적으로 말하자면 이진 검색은 O(logn)의 복잡도를 나타낸다. 선형 검색보다 복잡도가 훨씬 낫다. 하지만 이 알고리즘을 사용하는 데에는 전제 조건이 있다. 전체 배열이 정렬되어있어야 한다. 

 

말로 풀어서 설명하면 이렇다. (전제 : 정렬된 배열)

1. 배열의 가운데 값과 검색하고자 하는 값을 비교한다.

2. 만약 검색하고자 값이 더 크다면 가운데 값보다 작은 부분들은 살펴볼 필요가 없다. 즉, 검색 후보군을 절반으로 줄인다.

   작은 경우에는 반대로 큰 쪽 절반을 살펴볼 필요가 없다.

3. 그런식으로 반복해서 검색하고자 하는 값을 찾고 없다면 -1을 출력한다.

 

Write a function called binarySearch which accepts a sorted array and a value and returns the index at which the value exists. Otherwise, return -1.

binarySearch([1,2,3,4,5],2) // 1
binarySearch([1,2,3,4,5],3) // 2
binarySearch([1,2,3,4,5],5) // 4
binarySearch([1,2,3,4,5],6) // -1
binarySearch([, 6, 10, 13, 14, 18, 30, 34, 35, 37, 40, 44, 64, 79, 84, 86, 95, 96, 98, 99], 10) // 2
binarySearch([5, 6, 10, 13, 14, 18, 30, 34, 35, 37, 40, 44, 64, 79, 84, 86, 95, 96, 98, 99], 95) // 16
binarySearch([5, 6, 10, 13, 14, 18, 30, 34, 35, 37, 40, 44, 64, 79, 84, 86, 95, 96, 98, 99], 100) // -1

 

나의 답

function binarySearch(sortedArr, num){

// 포인터를 두개 설정
  let left = 0
  let right = sortedArr.length - 1
  while(left<=right){
  	//가운데값과 비교
      let mid= Math.floor((left+right)/2)
      if(sortedArr[mid] === num){
          return mid
      } 
      // 검색값이 더 클 경우 왼쪽 포인터를 이동
      if(sortedArr[mid] < num){
          left = mid + 1
      }
      // 검색값이 더 작을 경우 오른쪽 포인터를 이동
      if(sortedArr[mid] > num){
          right= mid - 1
      }
  }
  return -1
}

포인터를 접목시키면 아주 간단하게 해결된다. 왼쪽 끝, 오른쪽 끝 포인터 2개를 설정한 후 두개가 겹칠 때까지 검색을 한다.

 

제시되어있는 첫번째 예시를 가지고 설명을 하자면, left=0, right=4를 가리킨다. 그리고 둘의 평균값이 2이기 때문에 인덱스가 2인 3이 중간값이 된다. 그 다음 검색값이 2와 비교하면 검색값이 더 작기 때문에 3보다 큰 부분인 4,5는 살펴볼 필요가 없다. 그렇기 때문에 right를 중간값의 바로 왼쪽값인 1로 이동시킨다.

그 다음 반복문을 돌게 되면 mid=0이 되고 2는 1보다 더 크기 때문에 left를 중간값보다 하나 오른쪽인 1로 이동시킨다.

그 다음 여전히 반복문의 조건문이 참이기 때문에 한 번 더 돌게 되면 mid=1이 되어 2와 일치하고 인덱스값인 mid를 출력하게 된다. 

 

5개의 후보군 중에서 총 3번의 검색을 통해서 값을 찾게 되었다.

만약 32개의 후보군이라면 5번만 검색하면 값의 유무와 인덱스값까지 확인할 수 있게 된다.

선형 알고리즘보다 획기적으로 짧은 시간이 걸리게 된다.

정렬되어있다는 전제조건만 성립한다면 이진 검색 알고리즘은 정말 강력한 힘을 발휘할 것이다.