[개념] 검색알고리즘 (선형 VS 이진)

검색 알고리즘

우리는 프로젝트를 하던 알고리즘 문제를 풀던 어떠한 값을 찾기위해서 배열 또는 객체를 만들어서 그 값을 찾는 로직을 구현을 하는 모습을 자주 보인다.

 

그렇다면 이러한 검색을 하기위해서 가장 최적의 방법은 무엇일까? 에 대한 고민을 한번쯤은 해봐야 한다.

 

---

선형검색 알고리즘(linear search)

아래 이미지는 선형검색 알고리즘의 실행 과정을 보여준다.

선형검색 알고리즘은 0번째 index부터의 비교를 통해서 값을 찾을 수 있다

• 장점
  • 값을 추가할 때 강점이 있음
  • 간단하고 직관적인 코드 (걍 반복문 돌리면 됨)
• 단점
  • 크기가 커질수록 step이 비례적으로 증가하기때문에 점진적으로 비효율적으로 되어버림
  • 최악의수로는 배열의 마지막 index에 위치한 값을 찾는 것이다.

function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) {
      return i; // 원하는 값의 인덱스 반환
    }
  }
  return -1; // 찾지 못했을 경우 -1 반환
}

---

 

이진검색 알고리즘(Binary search)

비례적으로 step의 증가로 인해서 좋지못한 성능이 되어버리는 선형알고리즘에서 발전 된 알고리즘이라고 할 수 있다.

중간에서부터 값을 찾아가는 알고리즘으로써 반토막내서 필요없는 부분을 버리기 때문에 선형검색보다 훨씬 빠르게 원하는 값을 찾을 수 있다.

• 장점
  • 선형검색에 비해 속도가 매우 빠르다
• 단점
  • 정렬된 배열에서만 사용할 수 있다.

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);

    if (arr[mid] === target) {
      return mid; // 원하는 값의 인덱스 반환
    } else if (arr[mid] < target) {
      left = mid + 1; // 중앙값보다 크면 왼쪽 범위 제외
    } else {
      right = mid - 1; // 중앙값보다 작으면 오른쪽 범위 제외
    }
  }

  return -1; // 찾지 못했을 경우 -1 반환
}

---

우리가 평소 프로젝트를 하게 된다면 기본형단계의 정렬된 값을 사용하는 것이 아닌 배열의 형태로 특정값을 기준으로 (postId순서?) 정렬된 값을 사용할테니 사실상 나는 알고리즘을 풀때나 많이 사용하게 되는 부분이겠구나 라는 생각이 많이 들었음.