-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy paththree.py
More file actions
45 lines (35 loc) ยท 1.44 KB
/
three.py
File metadata and controls
45 lines (35 loc) ยท 1.44 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
import random
import time
def three_search(arr, target, low, high):
if low > high:
return -1 # ์์ดํ
์ด ์์
third = (high - low) // 3 # 3๋ฑ๋ถ์ผ๋ก ๋๋๊ธฐ
first_third = low + third # ์ฒซ๋ฒ์งธ ๋ถ๋ถ
second_third = high - third # ๋๋ฒ์งธ ๋ถ๋ถ
if arr[first_third] == target: # ๋๋๋ ๊ธฐ์ค์ด ์ฐพ๋ ๊ฐ์ผ ๊ฒฝ์ฐ
return first_third
if arr[second_third] == target: # ๋๋๋ ๊ธฐ์ค์ด ์ฐพ๋ ๊ฐ์ผ ๊ฒฝ์ฐ
return second_third
if target < arr[first_third]: # ์ฒซ ๋ถ๋ถ ๊ธฐ์ค๋ณด๋ค ์ฐพ๋ ๊ฐ์ด ์์ ๊ฒฝ์ฐ
return three_search(arr, target, low, first_third - 1)
elif target > arr[second_third]: # ๋๋ฒ์งธ ๋ถ๋ถ ๊ธฐ์ค๋ณด๋ค ์ฐพ๋ ๊ฐ์ด ํฐ ๊ฒฝ์ฐ
return three_search(arr, target, second_third + 1, high)
else: # ๊ฐ์ด๋ฐ ๋ถ๋ถ์ ์์ ๊ฒฝ์ฐ
return three_search(arr, target, first_third + 1, second_third - 1)
# ๋ฐฐ์ด ์์ฑ ๋ฐ ์ ๋ ฌ
n = 1000000
s = [random.randint(0, n) for _ in range(n)]
s.sort()
print("์ ๋ ฌ๋ ๋ฆฌ์คํธ:", s)
# ์ฐพ์ ํ๊ฒ ๊ฐ๋ ๋๋ค์ผ๋ก ์ค์
target = random.choice(s)
print("์ฐพ์ ๊ฐ:", target)
#์ํ ์๊ฐ ์์
start = time.time()
# ๊ฒ์ ์คํ
result = three_search(s, target, 0, len(s) - 1)
#์ํ ์๊ฐ ๋
end = time.time()
# ๊ฒฐ๊ณผ ์ถ๋ ฅ
print(f"์ฐพ์ ์ธ๋ฑ์ค: {result}" if result != -1 else "์์ดํ
์ด ๋ฆฌ์คํธ์ ์์ต๋๋ค.")
print(f"์ํ ์๊ฐ: {end - start:.10f}์ด")