Algorithm - CodeKata #20 ๐
1. ์ด์งํ์๋ฒ(Binary Search)
์ด์งํ์์ ๋ฐฐ์ฐ๊ธฐ ์ ์ ์ ํํ์(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
const nums = [-1,0,3,5,9,12];
const target = 9;
const search = (nums, target) => {
let low = 0
let high = nums.length - 1
while (low <= high) {
let mid = Math.floor((low + high) / 2)
if (nums[mid] < target) {
low = mid + 1
} else if (nums[mid] > target) {
high = mid - 1
} else {
return mid
}
}
return -1
}
search(nums, target); // 4
Author And Source
์ด ๋ฌธ์ ์ ๊ดํ์ฌ(Algorithm - CodeKata #20 ๐), ์ฐ๋ฆฌ๋ ์ด๊ณณ์์ ๋ ๋ง์ ์๋ฃ๋ฅผ ๋ฐ๊ฒฌํ๊ณ ๋งํฌ๋ฅผ ํด๋ฆญํ์ฌ ๋ณด์๋ค https://velog.io/@devmoonsh/JavaScript-CodeKata-20์ ์ ๊ท์: ์์์ ์ ๋ณด๊ฐ ์์์ URL์ ํฌํจ๋์ด ์์ผ๋ฉฐ ์ ์๊ถ์ ์์์ ์์ ์ ๋๋ค.
์ฐ์ํ ๊ฐ๋ฐ์ ์ฝํ ์ธ ๋ฐ๊ฒฌ์ ์ ๋ (Collection and Share based on the CC Protocol.)
์ข์ ์นํ์ด์ง ์ฆ๊ฒจ์ฐพ๊ธฐ
๊ฐ๋ฐ์ ์ฐ์ ์ฌ์ดํธ ์์ง
๊ฐ๋ฐ์๊ฐ ์์์ผ ํ ํ์ ์ฌ์ดํธ 100์ ์ถ์ฒ ์ฐ๋ฆฌ๋ ๋น์ ์ ์ํด 100๊ฐ์ ์์ฃผ ์ฌ์ฉํ๋ ๊ฐ๋ฐ์ ํ์ต ์ฌ์ดํธ๋ฅผ ์ ๋ฆฌํ์ต๋๋ค