Home > Archive > DataStructure > πŸ“¦[DataStructure] λ³€μˆ˜μ™€ 배열이 μ€‘μš”ν•œ μ΄μœ μ™€ 이진 탐색

πŸ“¦[DataStructure] λ³€μˆ˜μ™€ 배열이 μ€‘μš”ν•œ μ΄μœ μ™€ 이진 탐색
DataStructure

λ³€μˆ˜μ™€ 배열이 μ€‘μš”ν•œ 이유.

λ³€μˆ˜μ™€ 배열은 μ΄ˆκΈ‰ ν”„λ‘œκ·Έλž˜λ° μˆ˜μ—…μ˜ ν•„μˆ˜ μš”μ†Œμ΄λ©°, κ·Έλž˜μ„œ μž¬λ―Έμ—†μ–΄ 보일 수 μžˆμ§€λ§Œ 컴퓨터 ν”„λ‘œκ·Έλž˜λ°κ³Ό 자료 ꡬ쑰의 근간을 μ œκ³΅ν•˜κΈ° λ•Œλ¬Έμ— κΌ­ 탐ꡬ해야 ν•  μ€‘μš”ν•œ κ°œλ…μž…λ‹ˆλ‹€.

  • 또 이런 κ°œλ…μ€ μ•Œκ³ λ¦¬μ¦˜μ— λ―ΈμΉ˜λŠ” 동적 자료 ꡬ쑰의 영ν–₯을 ν‰κ°€ν•˜λŠ” 기쀀을 μ œκ³΅ν•©λ‹ˆλ‹€.

이진 탐색(binary search).

이진 탐색(binary search) 은 μ •λ ¬λœ λ¦¬μŠ€νŠΈμ—μ„œ νŠΉμ • 값을 λΉ λ₯΄κ²Œ μ°ΎλŠ” μ•Œκ³ λ¦¬μ¦˜μž…λ‹ˆλ‹€.

  • 이 μ•Œκ³ λ¦¬μ¦˜μ€ 리슀트λ₯Ό 반으둜 λ‚˜μ›Œμ„œ λͺ©ν‘―값이 μ–΄λŠ μͺ½ μ ˆλ°˜μ— μ†ν•˜λŠ”μ§€ κ²°μ •ν•˜κ³ , λ‚˜λ¨Έμ§€ μ ˆλ°˜μ€ λ²„λ¦¬λ©΄μ„œ λͺ©ν‘―값이 포함될 κ°€λŠ₯성이 μžˆλŠ” μ ˆλ°˜μ„ νƒμƒ‰ν•˜λŠ” λ°©μ‹μœΌλ‘œ λ™μž‘ν•©λ‹ˆλ‹€.

이 μ•Œκ³ λ¦¬μ¦˜μ˜ κ΅¬ν˜„ 방법과 논리적 간결성은 컴퓨터 κ³Όν•™ μž…λ¬Έ κ³Όλͺ©μ— μ ν•©ν•˜κΈ° λ•Œλ¬Έμ— 거의 λͺ¨λ“  컴퓨터 κ³Όν•™ κ΅κ³Όμ„œμ™€ κ°•μ˜μ—μ„œ 이진 탐색 μ•Œκ³ λ¦¬μ¦˜μ„ λ‹€λ£Ήλ‹ˆλ‹€.

β€œμ •λ ¬λœ λ¦¬μŠ€νŠΈμ—μ„œ νƒμƒ‰ν•˜λŠ” 일이 μ–Όλ§ˆλ‚˜ 자주 μžˆμ„κΉŒ?” ν˜Ήμ€ 더 ꡬ체적으둜 β€œλ‚΄ μ •λ ¬λœ λ¦¬μŠ€νŠΈμ—μ„œ 탐색 ν•¨μˆ˜λ₯Ό 직접 κ΅¬ν˜„ν•  일이 μ–Όλ§ˆλ‚˜ 자주 μžˆμ„κΉŒ? 이미 수백만 λͺ…이 이 짓을 ν•˜μ§€ μ•Šμ•˜λ‚˜? λΌμ΄λΈŒλŸ¬λ¦¬μ— μžˆμ§€ μ•Šμ€κ°€?” 라고 생각할 μˆ˜λ„ μžˆμŠ΅λ‹ˆλ‹€.

  • ν•˜μ§€λ§Œ μ–Έμ  κ°€ μžμ‹ λ§Œμ˜ 이진 탐색이 ν•„μš”ν•  κ°€λŠ₯성을 λ°°μ œν—€μ„œλŠ” μ•ˆ 되며, 이진 νƒμƒ‰μ˜ μ§„μ •ν•œ μ€‘μš”μ„±μ€ λ‹¨μˆœνžˆ 이진 탐색을 κ΅¬ν˜„ν•˜λŠ” 일을 λ„˜μ–΄μ„­λ‹ˆλ‹€.

이진 탐색은 λ˜‘λ˜‘ν•œ μ•Œκ³ λ¦¬μ¦˜μ΄ μ •λ ¬λœ λ°μ΄ν„°μ²˜λŸΌ μ•„μ£Ό λ‹¨μˆœν•œ 자료 μ£Όκ³ μ—μ„œ μ‘°μ°¨ 데이터가 μ €μž₯λ˜μ–΄ μžˆλŠ” ꡬ쑰λ₯Ό ν™œμš©ν•΄ μƒλ‹Ήν•œ 계산 λΉ„μš©μ„ μ ˆμ•½ν•  수 μžˆμŒμ„ λ³΄μ—¬μ£ΌλŠ” μ˜ˆμž…λ‹ˆλ‹€.

  • 이진 탐색은 μ •ν™•μ„±κ³Ό νš¨μœ¨μ„±μ„ μ‰½κ²Œ 뢄석할 수 있고 속도와 μ •ν™•μ„± λͺ¨λ‘λ₯Ό 보μž₯ν•˜λ©° 데이터와 μ•Œκ³ λ¦¬μ¦˜μ˜ μƒν˜Έ μž‘μš©μ„ 잘 λ³΄μ—¬μ€λ‹ˆλ‹€.
    • κ·Έλ ‡κΈ° λ•Œλ¬Έμ— 이진 탐색은 μ—°κ²° 리슀트, λ°°μ—΄, κ·Έ μ™Έμ˜ μ—¬λŸ¬ 트리 기반 μ•Œκ³ λ¦¬μ¦˜κ³Ό 같은 데이터 μ €μž₯ κΈ°λ²•λ“€μ˜ 차이점을 μ‚΄νŽ΄λ³΄λŠ” ν›Œλ₯­ν•œ λ Œμ¦ˆκ°€ 될 수 μžˆμŠ΅λ‹ˆλ‹€.