누구나 자료구조와 알고리즘 - (2) 알고리즘이 중요한 까닭: 선형 검색과 이진 검색

 

 

 

 

 

 

올바른 자료구조의 선택은 중요하다.

알고리즘은 어려운 단어같지만 단순히 "어떤 과제를 완수하는 명령어 집합"이라고 생각하면 된다.

 

 

 

---

 

 

정렬된 배열

정렬된 배열(ordered array)는 전형적인 배열과 거의 같지만 차이점은 값이 순서대로 있어야 한다는 점이다.

전형적인 배열
[17, 37, 5, 202, 80]

정렬된 배열
[3, 17, 75, 80, 202]

 

1.1. 삽입

값을 정렬된 배열에 삽입하는 경우 전형적인 배열과 비교하면 덜 효율적이다.

 

1.2. 검색

1.2.1. 선형검색

원하는 값을 찾을 때 까지 왼쪽에서 오른쪽으로 한 번에 한 셀씩 확인하는 방법을 "선형 검색"이라고 한다.

선형 검색은 알고리즘 중 하나이다.

 

🔎 선형 검색에서 두 배열의 차이점

정렬된 배열	전형적인 배열
값이 배열에 들어있지 않을 때 검색을 더 빨리 멈출 수 있다. 예를 들어, 위의 정렬된 배열에서 22를 찾으려고 할 때 75에 도달하면 더 이상 22가 오른쪽에 있을 수 없으므로 바로 검색을 중단할 수 있다.	찾는 값이 배열 어디에든 있을 수 있으므로 모든 원소를 하나도 빠짐없이 검색해야 한다.

따라서 최악의 시나리오인 요소가 배열 끝에 존재하는 경우가 아니라면 전형적인 배열보다 효율적인 방법이다.

 

 

1.2.2. 이진 검색

이진 검색에서 더 뚜렷한 차이가 나타난다.

배열의 길이를 2로 나누어 가운데 셀 인덱스를 구해 가운데부터 검색을 시작한다. 예를 들어, 위의 정렬된 배열에서는 75가 가운데 인덱스이며, 찾는 값이 22일 경우 75를 기준으로 후반의 모든 셀은 제거된다. 다시 임의의 값을 찾고 값이 해당될 리 없는 전, 후의 셀은 제거된다.

이진 검색은 정렬된 배열에서만 사용할 수 있다.

export const binarySearch = (array, searchValue) => {
  let lowerBound = 0
  let upperBound = array.length - 1

  while (lowerBound <= upperBound) {
    const midpoint = Math.floor((lowerBound + upperBound) / 2) // 배열의 가운데 값
    const valueAtMidpoint = array[midpoint] // 중간 지점의 값

    if (searchValue === valueAtMidpoint) {
      return midpoint
    } else if (searchValue < valueAtMidpoint) {
      upperBound = midpoint - 1
    } else {
      lowerBound = midpoint + 1
    }
  }

  return null
}

 

 

💡 이진 검색 대 선형 검색

원소가 10,000개인 배열에서 선형 검색은 최대 10,000단계가 걸리지만 이진 검색은 최대 13단계면 충분하다.
사용자의 어플리케이션에 어떤 구조가 더 좋은지 알려면 항상 분석하고 있어야 한다.

 

 

 

---

출처

제이 웹그로우, 누구나 자료구조와 알고리즘 (길벗, 2021)

 

 

 

 

---

개인적으로 공부한 내용을 정리하는 블로그로
잘못된 개념을 게시하지않도록 주의하고 있으나 오류가 있을 수 있습니다.