[JS 알고리즘] 순차 탐색과 이진 탐색

순차 탐색이란?

• 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 하나씩 확인하는 탐색법이다.
• 시간복잡도는 O(N)이다.

이진탐색이란?

• 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다.
• 시간 복잡도는 O(log N)이다.

https://blog.naver.com/jkssleeky/220715543451

• 각 단계마다 탐색 범위를 2로 나누며, 범위가 반으로 감소하므로 로그 복잡도를 가진다.

이진 탐색을 사용할 때 좋은 점

1. 넓은(억 단위 이상)탐색 범위에서 최적의 해를 찾아야 하는 경우
2. 데이터를 정렬한 뒤에 다수의 쿼리를 날려야하는 경우

const binarySearch = (arr, target, start, end) => {
  if (start > end) return -1;
  let mid = parseInt(start + end / 2);
  if (arr[mid] === target) return mid;
  //target이 중간값보다 작으니깐, 왼쪽을 탐색하자
  else if (arr[mid] > target) binarySearch(arr, target, start, mid - 1);
  //아니면 오른쪽을 탐색하자
  else binarySearch(arr, target, mid + 1, end);
};

let target = 5;
let arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
let result = binarySearch(arr, target, 0, arr.length - 1);
if (result === -1) console.log("원소 없음");
else console.log(`${result + 1}번째 존재`);