컴퓨터 공학

선형 검색과 이진 검색이 무엇일까

2023년 2월 14일1 min read

선형검색

처음부터 끝까지 배열들을 순회하면서 일치하는 것을 찾아낸다
메서드로는 indexOf includes등이 있다

예시로 indexOf를 만들어 보자

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

  return -1;
}

arr와 찾고자 하는 value만 넣으면 해당 인덱스를 반환하거나 없다면 -1를 리턴하는 함수이다

이것이 바로 선형 검색이다

이보다 발전된 이진 검색도 있다
한 번 살펴보자

이진검색

이진 검색은 정렬이 되어있어야만 적용이 가능하다
기본적인 개념은 분할 정복이다
보통 중간지점을 선택하고 찾고자 하는 값과 비교후
중간지점 앞 뒤로 나눈다 그렇게 값을 찾을 때 까지 반복한다

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