์ด์งํ์(Binary Search) ์ ๋ ฌ๋ ์ํ์ ์ ๋ ฅ ๋ฐ์ดํฐ์ ๋ํ ํจ๊ณผ์ ์ธ ํ์ ๋ฐฉ๋ฒ ์ค๋ฆ์ฐจ์ ํ์ ๋ฐฉ๋ฒ ๋ฐฐ์ด์ ๊ฐ์ด๋ฐ ์์ A[x]์ ํ์ํค y๋ฅผ ๋น๊ต. 1) ํ์ํค = ๊ฐ์ด๋ฐ ์์ -> ํ์ ์ฑ๊ณต(์ธ๋ฑ์ค x)๋ฅผ ๋ฐํ ํ ์ข ๋ฃ 2) ํ์ํค '์ด์ง ํ์(์๋ ํฌ๊ธฐ 1/2์ธ ์ผ์ชฝ ๋ถ๋ถ ๋ฐฐ์ด) ': ์ํํธ์ถ 3) ํ์ํค '์ด์ง ํ์(์๋ ํฌ๊ธฐ 1/2์ธ ์ค๋ฅธ์ชฝ ๋ถ๋ถ ๋ฐฐ์ด) ': ์ํํธ์ถ ์์ T(n) = T(n/2) + O(1) (n > 1), T(1) = 1 T(n) = O(logn) ํน์ง ๋ฐฐ์ด์ ๋ฐ์ดํฐ๊ฐ ์ ๋ ฌ๋ ๊ฒฝ์ฐ์๋ง ์ ์ฉ. ์ฝ์ / ์ญ์ ์ฐ์ฐ์ ๋ถ๊ฐ์ ์ธ ๋ฐ์ดํฐ ์ด๋์ ์๋ฐ. ๋ฐ์ดํฐ์ ์ ๋ ฌ ์ํ ์ ์ง๋ฅผ ์ํด์ ํ๊ท n/2๊ฐ์ ๋ฐ์ด..