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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
| #!/usr/bin/env python3
# -*- coding:utf-8 -*-
import bisect
def binary_search(arr, target):
""" 二分查找不存在返回 -1 """
ret = -1
if not arr:
return ret
arr_len = len(arr)
left = 0
right = arr_len
while left < right:
mid = left + ((right - left)>>1)
v = arr[mid]
if v < target:
left = mid + 1
elif v > target:
right = mid
else:
return mid
return ret
def low_bound(arr, target):
""" 返回左边界 第一个大于等于 """
ret = -1
if not arr:
return ret
arr_len = len(arr)
left = 0
right = arr_len
while left < right:
mid = left + ((right - left)>>1)
v = arr[mid]
# v >= target right = mid
if v < target:
left = mid + 1
elif v > target:
right = mid
else:
right = mid
ret = left
return ret
def upper_bound(arr, target):
""" 返回边界 第一个大于"""
ret = -1
if not arr:
return ret
arr_len = len(arr)
left = 0
right = arr_len
while left < right:
mid = left + ((right - left)>>1)
v = arr[mid]
# v <= target left = mid + 1
if v < target:
left = mid + 1
elif v > target:
right = mid
else:
left = mid + 1
ret = right
return ret
def low_bound_reverse(arr, target):
""" 逆序数组，返回左边界 第一个小于等于 """
ret = -1
if not arr:
return ret
arr_len = len(arr)
left = 0
right = arr_len
while left < right:
mid = left + ((right - left)>>1)
v = arr[mid]
# v >= target left = mid + 1
if v >= target:
left = mid + 1
elif v < target:
right = mid
ret = left
return ret
def upper_bound_reverse(arr, target):
""" 逆序数组，返回边界 第一个小于"""
ret = -1
if not arr:
return ret
arr_len = len(arr)
left = 0
right = arr_len
while left < right:
mid = left + ((right - left)>>1)
v = arr[mid]
# v <= target right = mid
if v > target:
left = mid + 1
elif v <= target:
right = mid
ret = right
return ret
def _main():
# arr = list(range(1, 11))
# 数组从小到大
arr = list(range(11))
pivot = 7
arr[8] = pivot
print('origin: {}'.format(arr))
for i in (-1, 5, 7, 8, 11):
ret1 = binary_search(arr, i)
ret2 = bisect.bisect_left(arr, i)
print('{} diff {} {}'.format(i, ret1, ret2))
for i in (-1, 5, 7, 8, 11):
ret1 = low_bound(arr, i)
ret2 = bisect.bisect_left(arr, i)
print('{} diff {} {}'.format(i, ret1, ret2))
for i in (-1, 5, 7, 8, 11):
ret1 = upper_bound(arr, i)
ret2 = bisect.bisect_right(arr, i)
print('{} diff {} {}'.format(i, ret1, ret2))
arr.sort(reverse=True)
print('sort origin: {}'.format(arr))
for i in (-1, 5, 7, 8, 11):
ret1 = low_bound_reverse(arr, i)
# ret2 = bisect.bisect_left(arr, i)
# ret3 = bisect.bisect_right(arr, i)
# ret2 = ret2 if ret2 < ret3 else ret3
ret2 = 0
print('{} diff {} {}'.format(i, ret1, ret2))
for i in (-1, 5, 7, 8, 11):
ret1 = upper_bound_reverse(arr, i)
# ret2 = bisect.bisect_left(arr, i)
# ret3 = bisect.bisect_right(arr, i)
# ret2 = ret2 if ret2 > ret3 else ret3
ret2 = 0
print('{} diff {} {}'.format(i, ret1, ret2))
if __name__ == '__main__':
_main()
|