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

์ข‹์€ ์›นํŽ˜์ด์ง€ ์ฆ๊ฒจ์ฐพ๊ธฐ