hapter4-binary-search-algorithm
二分查找
普通二分与变种
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
28def binarySearch():
nums, key = [1,2,3,4,5], 3
def common():
left, right = 0, len(nums)
while(left <= right):
mid = left + (right-left)//2 #mid=(l + h)//2方式 可能出现加法溢出，也就是说加法的结果大于整型能够表示的范围，比如5 5 5
if key == nums[mid]:
return mid
if key > nums[mid]:
left = mid + 1
else:
right = mid - 1
return False
print(common())
#变种就是对边界进行判断
def variety():
left, right = 0, len(nums)
while (left < right):
mid = left + (right - left) // 2 # mid=(l + h)//2方式 可能出现加法溢出，也就是说加法的结果大于整型能够表示的范围，比如5 5 5
if key > nums[ mid ]:
left = mid + 1
else:
right = mid
return left
index = variety()
print(nums[index])
binarySearch()开平方
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
29def mySqrt():
x = 8
# 8开方sqrt是 2.82842 并且满足 sqrt = x/sqrt=(8/2.82842)==2。因为返回小于的那个数字，所以向下取整
# 并且结果sqrt一定属于[0,x]之间，因此用二分查找即可 当然对于一个开方来说
# 2^2(4)<8<3^2(8)一定是在连续两个数之间，且去小的哪一个，所以你懂的
def bs():
if x <= 1: return 0
left, right = 0, x
while(left <= right):
mid = left + (right - left)
sqrt = x/mid
if sqrt == mid:
return mid
if sqrt < mid:
right = mid - 1
else:
left = mid + 1
return right
print(bs())
#然后根据上诉逻辑化简可得
def mt():
if x <= 1: return x
sqrt = x
while sqrt > x/sqrt:
sqrt = (sqrt + x/sqrt)//2
return int(sqrt)
print(mt())
mySqrt()大于给定元素的最小元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16def nextGreatestLetter():
letters = ["c", "f", "j"]
target = "j"
if not letters:
return ''
left, right = 0, len(letters)
while(left <= right):
mid = left + (right - left) // 2
if letters[mid] > target:
right = mid - 1
else:
left = mid + 1
return letters[0] if left < len(letters) else letters[left]
nextGreatestLetter()有序数组的 Single Element
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
33def singleNonDuplicate():
nums = [1,1,2,3,3,4,4,8,8]
def solve1():
a = 0
for num in nums:
a ^= num
return a
def solve2():
return 2*sum(set(nums)) - sum(nums)
def solve3():
# 此题理解关键就在于他是成对切有序的。如果此时如果下标i为奇数位上(矩阵里的偶数数位)
# 如果nums[i] == nums[i+1]，那么必然前面的数是没有单的。所以成单的数一定是在矩阵的后面部分
# 因此这就可以转换为二分查找算法。我们先保证mid为偶数，那么判断条件就好写了
# 代码逻辑如下：
left, right = 0, len(nums) - 1
while(left < right):
mid = left + (right - left)//2
if mid % 2 != 0:
mid -= 1 # 保证 l / h / m 都在偶数位，使得查找区间大小一直都是奇数
if nums[mid] == nums[mid+1]:
left = mid + 2
elif nums[mid] != nums[mid+1]:
right = mid
print(nums[left])
return nums[left]
solve3()
singleNonDuplicate()第一个错误的版本
1
2
3
4
5
6
7
8
9
10
11
12
13
14def firstBadVersion():
n = 3
# 这里主要理解当版本出错，值为True时，说明第一出错的版本，在前面或者是本身。所以right = version
# 当版本为False时，出错的版本一定在后面。所以left = version + 1
# 因为right = version，不能够加减1，所以left<right为结束条件，这时候left存储的即为第一个出错的版本
left, right = 0, n
while(left < right):
version = left + (right - left)//2
if isBadVersion(version):
right = version
else:
left = version + 1
return left
firstBadVersion()旋转数组的最小数字
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
41def findMin():
nums = [3,4,5,1,2]
if not nums:
return 0
# 根据题意，由一点旋转，旋转的方式是不变的，满足nums[-1] < nums[0]
# 意为旋转后的数组第一个数一定是大于最后一个数的，并且最后一个数一定是在后面部分
# 因此利用最后一个数为轴心点，建立二分查找
# 代码逻辑为：
left, right = 0, len(nums)-1
while(left < right):
mid = left + (right - left)//2
if nums[mid] > nums[right]:
left = mid + 1
else:
right = mid
print(nums[left])
return nums[left]
findMin()
#剑指offer
class Solution:
def minArray(self, numbers: List[int]) -> int:
nums = numbers
if not nums:
return 0
# 根据题意，由一点旋转，旋转的方式是不变的，满足nums[-1] < nums[0]
# 意为旋转后的数组第一个数一定是大于最后一个数的，并且最后一个数一定是在后面部分
# 因此利用最后一个数为轴心点，建立二分查找
# 代码逻辑为：
left, right = 0, len(nums)-1
while(left < right):
mid = left + (right - left)//2
if nums[mid] > nums[right]:
left = mid + 1
elif nums[mid] < nums[right]:
right = mid
else:
right -= 1
# print(nums[left])
return nums[left]查找区间
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
39def searchRange():
nums = [ 5, 7, 7, 8, 8, 10 ];target = 8
# 在普通的二分查找方法中，left可总指向出现的第一个元素
# 如果对于target+1 那么查找的left指向target最后一个位置+1
# 因此，只需要两次二分查找，求出first和last位置即可。
# 代码逻辑如下：
def slove1():
def sr( nums, target ):
left, right = 0, len(nums) - 1
while (left <= right):
mid = left + (right - left) // 2
if nums[ mid ] < target:
left = mid + 1
if nums[ mid ] >= target:
right = mid - 1
print(left, right)
return left
first = sr(nums, target)
last = sr(nums, target + 1) - 1
print(first, last)
if first == len(nums) or nums[ first ] != target:
return [ -1, -1 ]
return [ first, max(first, last) ]
#这是什么算法？？？
def slove2():
if target not in nums:
return [-1,-1]
first = nums.index(target)
last = first
for i in range(first+1,len(nums)):
if nums[i] == target:
last += 1
return [first, max(first, last)]
slove2()
searchRange()