[Algorithm] 선형 검색과 이진 검색

선형 검색 (Linear Search)

다른 이름으로 순차 검색이라고도 하는 선형 검색이다.
선형 검색은 배열이나 데이터의 집합에서 처음부터 끝까지 순서대로 비교하여 원하는 값을 찾아내는 알고리즘이다.

순서대로 하나씩 비교하기 때문에 구현 난이도가 쉬운 편이고 보통 정렬되지 않은 데이터의 검색에서 사용한다. N개의 데이터에서 원하는 값이 N번째에 있다면 N번의 비교를 해야한다.

• 검색 시작 후 원하는 값을 바로 찾는 경우 Best Case, O(1)
• 마지막 N번째까지 찾는 Worst Case, O(n)

알고리즘 구현

for, while등 반복문을 통해 구현할 수 있지만 JavaScript에선 선형 검색을 위한 내장 메소드들이 있다.

• indexOf, includes, find, findIndex

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

function linearSearch(arr, target) {
  return arr.indexOf(target);
}

이진 검색 (Binary Search)

이진 검색은 선형 검색보다 크게 개선된 알고리즘이다. 중간 값을 지정해 한번 확인할 때마다 남은 데이터 항목의 절반을 없앨 수 있다. 하지만 이진 검색은 오름차순이나 내림차순, 알파벳 순서와 같이 정렬된 데이터에서만 사용해야 한다.

• 처음으로 선택한 중간 값이 원하는 값이 되는 경우 Best Case, O(1)
• Worst Case, O(log n)

알고리즘 구현

function binarySearch(arr, target) {
  let start = 0;
  let end = arr.length - 1;
  
  while( start <= end) {
    let mid = Math.floor((start + end) / 2);
    
    if( arr[mid] === target) return mid;
    
    if( arr[mid] > target) {
      end = mid - 1;
    } else {
      start = mid + 1;
    }
  }
  
  return -1;
}