[ Code Kata ] ๐Ÿคฏ python #20 ์ด์ง„ํƒ์ƒ‰๋ฒ•(Binary Search)

Haileeยท2020๋…„ 12์›” 27์ผ
0

[ Code Kata ]

๋ชฉ๋ก ๋ณด๊ธฐ
24/28
post-thumbnail

ํฌ๋ฆฌ์Šค๋งˆ์Šค์— ์ตํ˜”์–ด์•ผ ํ•  ์ƒˆ๋กœ์šด ์•Œ๊ณ ๋ฆฌ์ฆ˜, ์ด์ง„ํƒ์ƒ‰๋ฒ•!
์šฐ์„  ์ •๋ฆฌํ•ด๋‘๊ณ  ์ฐจ์ฐจ ์ตํ˜€๋ณด๋„๋ก ํ•˜์ž.

์„ค๋ช…์„ ์ฝ์–ด๋ณด๋ฉด ์•Œ๊ฒ ์ง€๋งŒ, 10000๊ฐœ์˜ ์š”์†Œ๊ฐ€ ๋“ค์–ด์žˆ๋Š” ๋ฆฌ์ŠคํŠธ ๋“ฑ์„ ๋Œ€์ƒ์œผ๋กœ ํƒ์ƒ‰ํ•˜๋ ค ํ•  ๋•Œ,
๋งค์šฐ ํšจ๊ณผ์ ์ธ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ผ ๊ฒƒ ๊ฐ™๋‹ค!

์ด์ง„ํƒ์ƒ‰๋ฒ•(Binary Search)

์ด์ง„ํƒ์ƒ‰์„ ๋ฐฐ์šฐ๊ธฐ ์ „์— ์„ ํ˜•ํƒ์ƒ‰(Linear Search)๋จผ์ € ๋ณด๊ฒ ์Šต๋‹ˆ๋‹ค.

์„ ํ˜•ํƒ์ƒ‰์ด๋‚˜, ์ด์ง„ํƒ์ƒ‰์˜ ์š”์†Œ๋Š” ์˜ค๋ฆ„์ฐจ์ˆœ์ด๋‚˜ ๋‚ด๋ฆผ์ฐจ์ˆœ์œผ๋กœ ๋˜์–ด ์žˆ์–ด์•ผ ์ ์šฉํ•  ์ˆ˜ ์žˆ๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ž…๋‹ˆ๋‹ค.

let arr = [2, 4, 6, 8, 11, 14];
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) ์ฐพ์•„์•ผํ•  ๊ฐ’๋ณด๋‹ค ํฌ๋ฉด ์™ผ์ชฝ์˜ ์ค‘๊ฐ„์—์„œ ๋‹ค์‹œ ๋น„๊ตํ•ฉ๋‹ˆ๋‹ค.
๋‹ค์‹œ ํ•œ ๋ฒˆ ํฌ๊ธฐ๋ฅผ ๋น„๊ตํ•ด์„œ ์˜ค๋ฅธ์ชฝ์˜ ์ค‘๊ฐ„์œผ๋กœ ๊ฐˆ์ง€, ์™ผ์ชฝ์˜ ์ค‘๊ฐ„์œผ๋กœ ๊ฐˆ์ง€ ๊ฒฐ์ •ํ•˜์—ฌ ๋‹ค์‹œ ์ฐพ์•„๋‚˜์„œ๋Š” ๊ฒƒ์„ ์ด์ง„ ํƒ์ƒ‰๋ฒ•์ด๋ผ๊ณ  ํ•ฉ๋‹ˆ๋‹ค.


์˜ค๋Š˜์˜ ์ฝ”๋“œ ์นดํƒ€

์˜ค๋ฆ„์ฐจ์ˆœ์ธ ์ˆซ์ž 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 = 9
Output: 4
Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
์„ค๋ช…: ์ฐพ์ง€ ๋ชปํ•˜๋ฉด -1๋กœ return ํ•ด์ฃผ์„ธ์š”.

nums ๋ฐฐ์—ด์— ์žˆ๋Š” ์š”์†Œ๋Š” ์„œ๋กœ ์ค‘๋ณต๋œ ๊ฐ’์ด ์—†์Šต๋‹ˆ๋‹ค.

model solution

def search(nums, target):
  l, r = 0, len(nums) - 1
  while l <= r:
    mid = (l + r) // 2
    if nums[mid] < target:
      l = mid + 1
    elif nums[mid] > target:
      r = mid - 1
    else:
      return mid
  return -1
profile
์›น ๊ฐœ๋ฐœ ๐Ÿท๐Ÿ˜Ž๐Ÿ‘Š๐Ÿป๐Ÿ”ฅ

0๊ฐœ์˜ ๋Œ“๊ธ€