검색 알고리즘

검색 알고리즘 다른 말로 탐색 알고리즘이라도 불리는 이 알고리즘에 대해 정리해보고자 한다.

 

기본적으로 공부한 내용에 의하면 두가지로 나뉘어지는데  1. 선형검색(Linear Search) 2.이진검색(Binary Search)

 

1. 선형 검색 (Linear Search)

선형검색은 기본적으로 맨 앞쪽부터 차례대로 검색하면서 타겟값과 맞는지 확인한다.

배열에 0 번째 인덱스 부터 검색하면서 올라간다.

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

console.log(LinearSearch([1, 2, 3, 4, 5, 6, 8], 6));

배열에 0번째 인덱스 부터 찿아 올라가면서 만약 target값과 arr[i] 값을 비교해서 값을 찿으면 인덱스를 반환해주고 ,

검색에 실패하면 -1을 리턴해준다.

 

2. 이진 검색(Binary Search)

이진 검색은 선형검색 처럼 0번째 인덱스 부터 확인하면서 검색하는게 아닌 중앙값을 찿아서 내가 찿으려는 값이

중앙값보다 큰지 작은지 확인해 가면서 찿는다.

이진 검색은 기본적으로 배열이 정렬 되어있어야 한다. 그리고 분할정복을 사용해서 값을 찿아 나선다.

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

start = 0 , end = 배열 끝 인덱스 

값 비교를 위해서 중앙값을 찿아야하는데 , 그냥 (start + end) / 2  이런식으로 하면 소수점이 나올 수 도 있기 때문에 

Math.floor() 사용해서 소수점을 때어준다.

 

[1,2,3,4,5] -> 5를 찿는 과정

(1)

처음 중앙값 : (0 + 4) / 2 = 2번째 인덱스 

5는 3보다 크기 때문에 start = 3 로 바꿔준다.

(2)

중앙값 : (3 + 4 ) / 2 = 3번째 인덱스 

5는 4보다 크기때문에 start = 4 로 바꿔준다.

(3)

중앙값 : (4 + 4) / 2 = 4번째 인덱스 

5는 5랑 같기 때문에 middle 값인 4를 리턴해준다.

그리고 start 값과 end값이 같아 졌기 때문에 while문이 종료 된다.