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

선형검색#

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

예시로 indexOf를 만들어 보자

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

6
  return -1;
7
}

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

이것이 바로 선형 검색이다

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

이진검색#

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

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

한동룡