검색

1.1 선형 검색

• 선형 검색(linear search)은 배열의 각 요소를 한 인덱스씩 순차적으로 접근하면서 동작한다.
• 선형 검색은 배열의 정렬 여부와 상관없이 동작하는 장점이 있지만, 배열의 모든 요소를 확인해야 하는 단점이 있다.
• 시간 복잡도 : O(n)

선형 검색을 통해 주어진 배열(array)에 주어진 값(target)이 요소로 존재하는지 확인하여 존재하는 경우 해당 인덱스를 반환하고 존재하지 않는 경우 -1을 반환하는 함수를 구현하라. 단, 어떠한 빌트인 함수도 사용하지 않고 for문을 사용하여 구현해야 한다.(array와 target은 모두 데이터 타입이 숫자이다)

문제 :

function linearSearch(array, target) {

}

console.log(linearSearch([1, 2, 3, 4, 5, 6], 1)); // 0
console.log(linearSearch([1, 2, 3, 4, 5, 6], 3)); // 2
console.log(linearSearch([1, 2, 3, 4, 5, 6], 5)); // 4
console.log(linearSearch([1, 2, 3, 4, 5, 6], 6)); // 5
console.log(linearSearch([1, 2, 3, 4, 5, 6], -1)); // -1
console.log(linearSearch([1, 2, 3, 4, 5, 6], 0)); // -1
console.log(linearSearch([1, 2, 3, 4, 5, 6], 7)); // -1

===

꼭 문제를 풀어보고 풀이를 살펴보자.

풀이 과정 :

먼저, for문을 이용해 배열의 요소를 하나하나 확인하며 target이 배열안에 있는지 확인해야 한다.
만약, 배열의 요소와 target이 일치한다면 해당하는 요소의 인덱스를 출력한다.

function linearSearch(array, target) {
  for( let i = 0; i < array.length; i++) {
    if( target === array[i] ) return i;
  }
}

console.log(linearSearch([1, 2, 3, 4, 5, 6], 1)); // 0
console.log(linearSearch([1, 2, 3, 4, 5, 6], 3)); // 2
console.log(linearSearch([1, 2, 3, 4, 5, 6], 5)); // 4
console.log(linearSearch([1, 2, 3, 4, 5, 6], 6)); // 5
console.log(linearSearch([1, 2, 3, 4, 5, 6], -1)); // -1
console.log(linearSearch([1, 2, 3, 4, 5, 6], 0)); // -1
console.log(linearSearch([1, 2, 3, 4, 5, 6], 7)); // -1

이렇게 작성하고 결과를 살펴보자.

0
2
4
5
undefined
undefined
undefined

target이 배열에 존재하는 경우는 잘 출력이 되는 반면, target이 배열 안에 존재하지 않는 경우는 undefined가 출력된다.

이 undefined는 어디서 나온 결과일까?

바로 함수의 return에서 나온다. 함수 몸체에 return문을 가지고 있지 않더라도 암묵적으로 undefined를 반환한다.

function linearSearch(array, target) {
  for( let i = 0; i < array.length; i++) {
    if( target === array[i] ) return i;
  }
  // => return undefined;
}

함수 몸체 제일 마지막 줄에 return이 없더라도 항상 return undefined;가 생략되어 있다고 생각하자.
위 코드를 해석하자면,

배열의 요소를 차례대로 검사하면서 target과 일치하는 것이 있는지 확인한다. 만약 일치한다면 i를 반환하면서 함수를 종료한다.
만약 존재하지 않는다면 함수를 끝내지 않고 for문을 빠져나와 return undefined;를 실행한다. 따라서 target이 배열에 존재하지 않는 경우는 undefined가 출력된다.

그럼 undefined 대신 -1을 출력하려면 어떻게 해야할까?
방법은 간단하게 return -1;을 함수 몸체 마지막에 적어주면 된다.

결과 :

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

console.log(linearSearch([1, 2, 3, 4, 5, 6], 1)); // 0
console.log(linearSearch([1, 2, 3, 4, 5, 6], 3)); // 2
console.log(linearSearch([1, 2, 3, 4, 5, 6], 5)); // 4
console.log(linearSearch([1, 2, 3, 4, 5, 6], 6)); // 5
console.log(linearSearch([1, 2, 3, 4, 5, 6], -1)); // -1
console.log(linearSearch([1, 2, 3, 4, 5, 6], 0)); // -1
console.log(linearSearch([1, 2, 3, 4, 5, 6], 7)); // -1

1.2 이진 검색

• 이진 검색(binary search)은 선형 검색과는 달리 정렬된 배열에서만 동작한다.
• 선형 검색은 배열의 모든 요소를 확인해야 하지만 이진 검색은 중간값과 검색 대상 값을 비교하여 검색 범위를 매번 반으로 줄여 나간다.
  • 검색 대상 값이 중간값보다 작은 경우 중간값보다 작은 쪽(왼쪽)을 검색 범위로 한정한다.
  • 검색 대상 값이 중간값보다 큰 경우 중간값보다 큰 쪽(오른쪽)을 검색 범위로 한정한다.
  • 검색 대상 값을 검색할 때까지 이와 같은 처리를 반복한다.
• 시간 복잡도 : O(log n)

이진 검색을 통해 주어진 배열(array)에 주어진 값(target)이 요소로 존재하는지 확인하여 존재하는 경우 해당 인덱스를 반환하고 존재하지 않는 경우 -1을 반환하는 함수를 구현하라. 단, 아래의 빌트인 함수 이외에는 어떤 빌트인 함수도 사용하지 않아야 하며, while문을 사용하여 구현하여야 한다.

• Math.floor: 전달받은 인수의 소수점 이하를 내림한 정수를 반환한다.

문제 :

function binarySearch(array, target) {

}

console.log(binarySearch([1, 2, 3, 4, 5, 6], 1)); // 0
console.log(binarySearch([1, 2, 3, 4, 5, 6], 3)); // 2
console.log(binarySearch([1, 2, 3, 4, 5, 6], 5)); // 4
console.log(binarySearch([1, 2, 3, 4, 5, 6], 6)); // 5
console.log(binarySearch([1, 2, 3, 4, 5, 6], -1)); // -1
console.log(binarySearch([1, 2, 3, 4, 5, 6], 0)); // -1
console.log(binarySearch([1, 2, 3, 4, 5, 6], 7)); // -1

풀이 :

function binarySearch(array, target) {

  var start = 0;
  var end = array.length - 1;
  while( start <= end ) {
    var mid = Math.floor((start + end) / 2 ); // index
    if (target > array[mid]) {
      start = mid + 1;
      
    } else if( target < array[mid]) {
      end = mid - 1;
    }
    else {
      return mid;
    }
  } 
  return -1;
}    


console.log(binarySearch([1, 2, 3, 4, 5, 6], 1)); // 0
console.log(binarySearch([1, 2, 3, 4, 5, 6], 3)); // 2
console.log(binarySearch([1, 2, 3, 4, 5, 6], 5)); // 4
console.log(binarySearch([1, 2, 3, 4, 5, 6], 6)); // 5
console.log(binarySearch([1, 2, 3, 4, 5, 6], -1)); // -1
console.log(binarySearch([1, 2, 3, 4, 5, 6], 0)); // -1
console.log(binarySearch([1, 2, 3, 4, 5, 6], 7)); // -1