JavaScript - CodeKata #20 πŸ“Œ

devmoonshΒ·2020λ…„ 10μ›” 6일
0

JavaScript

λͺ©λ‘ 보기
45/48
post-thumbnail

이진탐색을 배우기 전에 μ„ ν˜•νƒμƒ‰(Linear Search)λ¨Όμ € λ³΄κ² μŠ΅λ‹ˆλ‹€.

** μ„ ν˜•νƒμƒ‰μ΄λ‚˜, μ΄μ§„νƒμƒ‰μ˜ μš”μ†ŒλŠ” μ˜€λ¦„μ°¨μˆœμ΄λ‚˜ λ‚΄λ¦Όμ°¨μˆœμœΌλ‘œ λ˜μ–΄ μžˆμ–΄μ•Ό μ μš©ν•  수 μžˆλŠ” μ•Œκ³ λ¦¬μ¦˜μž…λ‹ˆλ‹€.

let arr = [2, 4, 6, 8, 11, 14];

μœ„μ˜ λ°°μ—΄μ—μ„œ μš”μ†Œκ°€ 8인것을 찾으렀면 μ–΄λ–»κ²Œ ν•΄μ•Όν• κΉŒμš”?
index 0μ—μ„œλΆ€ν„° 5κΉŒμ§€ μ°¨λ‘€λŒ€λ‘œ μš”μ†Œλ₯Ό ν™•μΈν•˜λ©΄μ„œ 8이 λ‚˜μ˜¬ λ•ŒκΉŒμ§€ for 문을 돌리면 λ©λ‹ˆλ‹€.
μ΄λ ‡κ²Œ 첫 index λΆ€ν„° ν•˜λ‚˜ν•˜λ‚˜ μ°Ύμ•„λ‚˜μ„œλŠ” 것을 μ„ ν˜•νƒμƒ‰μ΄λΌκ³  ν•©λ‹ˆλ‹€.

그런데 λ°°μ—΄μ˜ 길이가 1000이고, 1000μ΄λΌλŠ” μš”μ†Œλ₯Ό μ°Ύμ•„μ•Ό ν•˜λŠ”λ° arr[9999]에 1000이 μžˆλ‹€κ³  κ°€μ •ν•œλ‹€λ©΄ λͺ‡ 번의 for문이 λŒμ•„κ°ˆκΉŒμš”?
λ„€, 1000번 μž…λ‹ˆλ‹€.

μ΄λ ‡κ²Œ μ„ ν˜•νƒμƒ‰μ˜ 단점은 μš”μ†Œμ— 따라 탐색을 μ—¬λŸ¬ 번 ν•΄μ•Όν•  μˆ˜λ„ μžˆλ‹€λŠ” μ μž…λ‹ˆλ‹€.
즉, 1을 찾으렀면 for문을 ν•œ 번만 λŒλ €λ„ λ˜λŠ”λ°, 1000을 찾으렀면 for문을 1000번 λŒλ €μ•Ό ν•œλ‹€λŠ” λ§μž…λ‹ˆλ‹€.
λ§Œμ•½ forλ¬Έ 내뢀에 λ³΅μž‘ν•œ 계산이 λ“€μ–΄μžˆλ‹€λ©΄ 싀행속도가 λŠλ €μ§€κ³  νš¨μœ¨μ μ΄μ§€ μ•Šμ€ 둜직이 될 κ²ƒμž…λ‹ˆλ‹€.

그럼 μ’€ 더 효과적인 μ•Œκ³ λ¦¬μ¦˜μ΄ μžˆμ„κΉŒμš”?
λ„€! λ°”λ‘œ 이진 νƒμƒ‰μž…λ‹ˆλ‹€.

이진 탐색은 μˆœμ„œλŒ€λ‘œ μ°ΎλŠ” 것이 μ•„λ‹ˆλΌ, 쀑간뢀터 μ°Ύμ•„ λ‚˜μ„œλŠ” λ°©λ²•μž…λ‹ˆλ‹€.
λ§Œμ•½ μ•„λž˜μ™€ 같은 λ°°μ—΄μ—μ„œ 7을 μ°Ύμ•„μ•Ό ν•œλ‹€λ©΄,
첫 번째둜 쀑간 μœ„μΉ˜μ˜ μš”μ†Œλ₯Ό λΉ„κ΅ν•˜κ³ (7<14)μ°Ύμ•„μ•Όν•  값보닀 크면 μ™Όμͺ½μ˜ μ€‘κ°„μ—μ„œ λ‹€μ‹œ λΉ„κ΅ν•©λ‹ˆλ‹€.
λ‹€μ‹œ ν•œ 번 크기λ₯Ό λΉ„κ΅ν•΄μ„œ 였λ₯Έμͺ½μ˜ μ€‘κ°„μœΌλ‘œ κ°ˆμ§€, μ™Όμͺ½μ˜ μ€‘κ°„μœΌλ‘œ κ°ˆμ§€ κ²°μ •ν•˜μ—¬ λ‹€μ‹œ μ°Ύμ•„λ‚˜μ„œλŠ” 것을 이진 탐색법이라고 ν•©λ‹ˆλ‹€.


2. Question

μ˜€λ¦„μ°¨μˆœμΈ 숫자 nums λ°°μ—΄κ³Ό μ°Ύμ•„μ•Όν•  target을 인자둜 μ£Όλ©΄,
target이 λͺ‡ 번째 index인지 return ν•΄μ£Όμ„Έμš”.

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
μ„€λͺ…: 찾지 λͺ»ν•˜λ©΄ -1둜 return ν•΄μ£Όμ„Έμš”.
  • nums 배열에 μžˆλŠ” μš”μ†ŒλŠ” μ„œλ‘œ μ€‘λ³΅λœ 값이 μ—†μŠ΅λ‹ˆλ‹€.

3. Answer

to be updated

profile
Junior front-end developer

0개의 λŒ“κΈ€