-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathQuestion_2.py
More file actions
112 lines (73 loc) · 2.58 KB
/
Copy pathQuestion_2.py
File metadata and controls
112 lines (73 loc) · 2.58 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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#!/usr/bin/env python
# -*- encoding:utf-8 -*-
# -------------------
# 二分查找算法
# 在有序数组中找指定的元素
# 循环法
# -------------------
arr_list = [2,27,34,23,12,56,42,102]
arr_list.sort() #[2, 12, 23, 27, 34, 42, 56, 102]
# print arr_list
# def two_split_find_cycle(key,arr_list):
# keep_arr_list = arr_list
# while len(keep_arr_list) > 0:
# cmp_key_id = len(keep_arr_list)/2
# cmp_key = keep_arr_list[cmp_key_id]
# if cmp_key == key:
# return True
# elif cmp_key > key and cmp_key_id > 1:
# keep_arr_list = keep_arr_list[0:cmp_key_id-1] # arr_list[0:0] error
# elif cmp_key > key and cmp_key_id == 1:
# keep_arr_list = keep_arr_list[0:cmp_key_id]
# else:
# keep_arr_list = keep_arr_list[cmp_key_id+1::]
# return False
# print two_split_find_cycle(2,arr_list)
def two_split_find_cycle(key,arr):
start = 0
end = len(arr) -1
while start <= end:
mid = start + (end - start)/2
if arr[mid] > key:
end = mid - 1
if arr[mid] < key:
start = mid + 1
if arr[mid] == key:
return mid
return -1
print two_split_find_cycle(27,arr_list)
# --------------------
# 二分查找算法
# 在有序数组中找指定的元素
# 递归法
# --------------------
arr_list = [2,27,34,23,12,56,42,102]
arr_list.sort() #[2, 12, 23, 27, 34, 42, 56, 102]
# def two_split_find_recursive(key,arr_list):
# if len(arr_list) == 0:
# return False
# else:
# cmp_key_id = len(arr_list)/2
# cmp_key = arr_list[cmp_key_id]
# print "arr_list %s , cmp_key_id %s , cmp_key %s"%(arr_list,cmp_key_id,cmp_key)
# if cmp_key == key:
# return True
# elif cmp_key > key and cmp_key_id > 1:
# return two_split_find_recursive(key,arr_list[0:cmp_key_id])
# elif cmp_key > key and cmp_key_id == 1:
# return two_split_find_recursive(key,arr_list[0:cmp_key_id])
# else:
# return two_split_find_recursive(key,arr_list[cmp_key_id+1::])
# print two_split_find_recursive(23,arr_list)
def two_split_find_recursive(key,arr,start,end):
if start > end:
return -1
#print "start %s,end %s"%(start,end)
mid = start + (end - start)/2
#print "mid is %s"%(mid)
if arr[mid] > key:
return two_split_find_recursive(key,arr,start,mid-1)
if arr[mid] < key:
return two_split_find_recursive(key,arr,mid+1,end)
return mid
print two_split_find_recursive(42,arr_list,0,len(arr_list)-1)