์ด๋ถํ์์ ์ค๋ฆ์ฐจ์์ผ๋ก ์ ๋ ฌ๋ ๋ฐฐ์ด์์ ๋น ๋ฅด๊ฒ ํ์ํ๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ค.
์๊ฐ๋ณต์ก๋ : O(logN)
ํ์ํ ๊ฒ : ํ๊ฒ, ์์, ๋, ์ค๊ฐ
def ์ด์งํ์(ํ๊ฒ, ๋ฆฌ์คํธ): # ์ฐพ๋ ๊ฐ์ด ๋ช๋ฒ์งธ ์์์ ์๋ ์ง ๋ฐํํ๋ ํจ์
# ์ด๊ธฐ์ธํ
๋ฆฌ์คํธ.sort()
์์ = 0
๋ = len(arr)-1
while ์์<=๋: # ๋ชจ์์ด ์์ผ๋ฉด ๊ณ์
์ค๊ฐ = (์์+๋)//2
ํ์ฌ๊ฐ = ๋ฆฌ์คํธ[์ค๊ฐ]
if ํ์ฌ๊ฐ == ํ๊ฒ:
return ์ค๊ฐ
elif ํ์ฌ๊ฐ < ํ๊ฒ:
์์ = ์ค๊ฐ+1
elif ํ์ฌ๊ฐ > ํ๊ฒ:
๋ = ์ค๊ฐ -1
return none
์ดํด๊ฐ ์ฝ๋๋ก ๋ณ์๋ ํ๊ธ๋ก ์์ฑํ๋ค.
while ์์ ๋ด์ฉ์ ๊ณ์ํด์ [์ค๊ฐ]์ ํด๋นํ๋ ์์๊ฐ ํ๊ฒ๊ณผ ๊ฐ์์ง ๋ ๊น์ง ๊ณ์ ๋ฐ๋ณตํ๋ ๊ฒ์ด๋ค.
์ด๋ถํ์์ ์ง์ ๊ตฌํํ๋ ๋ฌธ์ ๊ฐ ์๋, ์ด๋ถํ์์ ์ฌ์ฉํด์ ํจ์จ์ฑ์ ๋์ฌ์ผ ํ๋ ๋ฌธ์ ์์๋ bisect๋ผ์ด๋ธ๋ฌ๋ฆฌ๋ฅผ ์ฌ์ฉํ๋ ๊ฒ์ด ์ ๋ฆฌํ๋ค.
์ฒ์์๋ ์ด๋ถํ์์ด ์ค์ํ๋ค๋ ์๊ฐ์ด ์์๋ค.
์ด๋ถํ์์ด ์๋๋ผ๋ ํ์ด๋ ๊ฐ๋ฅํ๊ธฐ ๋๋ฌธ์.
ํ์ง๋ง ํจ์จ์ฑ์ ํ ์คํธ ํ๋ค๋ฉด bisect๋ฅผ ๋ชฐ๋ผ์๋ ์๋๋ค.
[33, 99, 77, 70, 89, 90, 100]
๋ค์๊ณผ ๊ฐ์ด ์ฑ์ ์ด ์๊ณ
90์ ์ด์, 80์ ์ด์, 70์ ์ด์, 60์ ์ด์, ๋๋จธ์ง๋ก ์ฑ์ ์ ๋๋๋ค๋ฉด ์ด๋ถํ์์ผ๋ก ๊ฐ๋จํ๊ฒ ์ฒ๋ฆฌํ ์ ์๋ค.
์ ์์์์ ๋ฆฌ์คํธ์ for๋ฌธ์ ๋๋ ธ๋ค๊ณ ๊ฐ์ ํ์ ๋, ํ์ฌ ์์๊ฐ 77์ด๋ผ๋ฉด
bisect.bisect([60, 70, 80, 90], 77)
์ ํ๋ฉด 77์ด ์ ๋ ฌ๋์ด ์ฝ์
๋ ์ธ๋ฑ์ค์ธ 2
๊ฐ ๋ฐํ๋๋ค.
bisect์์ ํ๋จ๊ณ ๋ ์ ๊ทธ๋ ์ด๋ ๋ ๋ฒ์ ์ผ๋ก ์๊ฐํ๋ฉด ๋๋ค.
์๋๋ ํ์ ์ ๊ธฐ์ค์ด ์ด๋ค ์ ์ ์ด์์ด๋ผ๋ฉด
์ด์์ง๋ง ๋ง์ฝ ์ด๋ค ์ ์ ์ด๊ณผ๋ผ๋ฉด
์ผ๋ก ์กฐ๊ฑด์ด ๋ฐ๋๋ค๋ฉด bisect_left๋ฅผ ์จ์ผํ๋ค.
์๋ํ๋ฉด ์์์ ํ๊ฒ์ด ๊ฐ์ ๊ฒฝ์ฐ,
์๋ฅผ ๋ค์ด
bisect.bisect([60, 70, 80, 90], 70)
๋ 70์ ๋ค์ ์ธ๋ฑ์ค์ธ 2๋ฅผ ๋ฐํํ๋ฏ๋ก ๋ ๋์ ํ์ ์ ๋ฐ์ง๋ง,
bisect.bisect_left([60, 70, 80, 90], 70)
๋ 70์ ์ผ์ชฝ ์ธ๋ฑ์ค์ธ 1์ ๋ฐํํ์ฌ ํ๋จ๊ณ ๋ฎ์ ํ์ ์ ์ค ์ ์๊ธฐ ๋๋ฌธ์ด๋ค.
๋ํ ํ๊ฒ์ด ์ค์ ๊ทธ ๊ฐ์ ์ฐพ๋ ๋ฌธ์ ์ผ ๊ฒฝ์ฐ์๋ ์ ๋ต์ธ ์ธ๋ฑ์ค๋ฅผ ๋ฝ๊ธฐ ์ํด์๋ bisect_left๋ฅผ ์ฌ์ฉํด์ผํ๋ค.