社区微信群开通啦,扫一扫抢先加入社区官方微信群
社区微信群
python算法图解中的解释
通过不断迭代mid的值,来查找参数
def binary_search(nums,target):
# 确定lp和rp的索引值,从两边遍历查找
lp,rp = 0,len(nums)-1
while lp <= rp:
# 迭代求中间的索引值
mid = lp + (rp - lp) // 2
# 如果target等于中间值,返回中间值的索引
if nums[mid] == target:
return mid
# 如果target大于中间值,说明target在中间值的右边
elif target > nums[mid]:
lp = mid + 1
# else最后一种情况,target小于中间值,在其左边,更新rp的值
else:
rp = mid - 1
return None
nums = [1,3,4,56,67,78,980]
print(binary_search(nums,980))
例题链接:
https://leetcode-cn.com/problems/search-in-rotated-sorted-array/
def xuanzhuan_search(nums,target):
lp,rp = 0,len(nums)-1
while lp <= rp:
mid = lp + (rp-lp)//2
if nums[mid] == target:
return mid
# 中间值大于lp的值,说明旋转点在中间值的右边
elif nums[mid] >= nums[lp]:
if nums[lp] <= target < nums[mid]:
rp = mid - 1
else:
lp = mid + 1
# 旋转点在中间值的左边
else:
if nums[mid] < target <= nums[rp]:
lp = mid + 1
else:
rp = mid - 1
return False
nums = [56,67,78,980,1,3,4]
print(xuanzhuan_search(nums,100))
https://leetcode-cn.com/problems/search-in-rotated-sorted-array-ii/
由于返回True or False
在重复值上可进行去重操作
class Solution(object):
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: bool
"""
nums = list(set(nums))
lp,rp = 0,len(nums)-1
while lp <= rp:
mid = lp + (rp-lp)//2
if nums[mid] == target:
return True
# 中间值大于lp的值,说明旋转点在中间值的右边
elif nums[mid] >= nums[lp]:
if nums[lp] <= target < nums[mid]:
rp = mid - 1
else:
lp = mid + 1
# 旋转点在中间值的左边
else:
if nums[mid] < target <= nums[rp]:
lp = mid + 1
else:
rp = mid - 1
return False
nums[mid]==nums[lp]==nums[rp]
该怎么处理class Solution(object):
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: bool
"""
lp,rp = 0,len(nums)-1
while lp <= rp:
mid = lp + (rp-lp)//2
if nums[mid] == target:
return True
# 中间值大于lp的值,说明旋转点在中间值的右边
elif nums[mid] == nums[lp] == nums[rp]:
lp += 1
rp -= 1
elif nums[mid] >= nums[lp]:
if nums[lp] <= target < nums[mid]:
rp = mid - 1
else:
lp = mid + 1
# 旋转点在中间值的左边
else:
if nums[mid] < target <= nums[rp]:
lp = mid + 1
else:
rp = mid - 1
return False
在我们继续分析之前,我们应该注意到,这个算法是分而治之策略的一个很好的例子。分和治意味着我们将问题分成更小的部分,以某种方式解决更小的部分,然后重新组合整个问题以获得结果。 当我们执行列表的二分查找时,我们首先检查中间项。如果我们正在搜索的项小于中间项,我们可以简单地对原始列表的左半部分执行二分查找。同样,如果项大,我们可以执行右半部分的二分查找。 无论哪种方式,都是递归调用二分查找函数。
不过这种递归调用的方法只能查找target值是否存在于数组中,而不能返回其索引或者下标值
def binarySearch(alist, item):
if len(alist) == 0:
return False
else:
midpoint = len(alist)//2
if alist[midpoint]==item:
return True
else:
if item<alist[midpoint]:
return binarySearch(alist[:midpoint],item)
else:
return binarySearch(alist[midpoint+1:],item)
testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42,]
print(binarySearch(testlist, 3))
print(binarySearch(testlist, 13))
def sequentialSearch(alist, item):
pos = 0
found = False
while pos < len(alist) and not found:
if alist[pos] == item:
found = True
else:
pos = pos + 1
return found
def sequentialsearch(nums,target):
for num in nums:
if num == target:
return True
return False
nums = [1, 2, 32, 8, 17, 19, 42, 13, 0]
print(sequentialsearch(nums,8))
print(sequentialsearch(nums,100))
testlist = [1, 2, 32, 8, 17, 19, 42, 13, 0]
print(sequentialSearch(testlist, 3))
print(sequentialSearch(testlist, 13))
def bubble_sort(nums):
for i in range(len(nums)):
for j in range(len(nums)-i-1):
if nums[j] > nums[j+1]:
nums[j],nums[j+1] = nums[j+1],nums[j]
return nums
nums = [123,34,231,456,678,343,1,3,56,768]
print(bubble_sort(nums))
def bubble_sort(nums):
for num in range(len(nums)-1,0,-1):
for j in range(num):
if nums[j] > nums[j+1]:
nums[j],nums[j+1] = nums[j+1],nums[j]
return nums
nums = [123,34,231,456,678,343,1,3,56,768]
print(bubble_sort(nums))
def select_sort(nums):
"""
选择排序:每次选择最小值
:param nums: list
:return: list
"""
for i in range(len(nums)-1):
# 确定当前要排序的位置下标
index = i
# 选择剩下数组里最小的数值,和当前下标值进行交换
for j in range(i+1,len(nums)):
if nums[j] < nums[index]:
index = j
nums[index],nums[i] = nums[i],nums[index]
return nums
nums = [123,34,231,456,678,343,1,3,56,768]
print(select_sort(nums))
你可能会看到选择排序与冒泡排序有相同数量的比较,因此也是 O(n^2)。 然而,由于交换数量的减少,选择排序通常在基准研究中执行得更快。 事实上,对于我们的列表,冒泡排序有 20 次交换,而选择排序只有 8 次。
def insert_sort(nums):
"""
将每次插入的值排序
:param nums:
:return:
"""
for i in range(1,len(nums)):
value = nums[i]
pre_index = i-1
while pre_index >= 0 and nums[pre_index] > value:
nums[pre_index+1] = nums[pre_index]
pre_index -= 1
nums[pre_index+1] = value
return nums
nums = [3,6,19,15,4,100,368,34,56,78,89]
print(insert_sort(nums))
def quick_sort(nums):
return qsort(nums,0,len(nums)-1)
def qsort(nums,left,right):
if left > right:
return nums
lp,rp = left,right
key = nums[left]
while lp < rp:
while lp < rp and nums[rp] >= key:
rp -= 1
nums[lp] = nums[rp]
while lp < rp and nums[lp] <= key:
lp += 1
nums[rp] = nums[lp]
nums[lp] = key
qsort(nums,left,lp-1)
qsort(nums,lp+1,right)
return nums
nums = [123,34,231,456,678,343,1,3,56,768]
print(quick_sort(nums))
def merge_sort(nums):
if len(nums) == 1:
return nums
mid = len(nums) // 2
return merge(merge_sort(nums[:mid]),merge_sort(nums[mid:]))
def merge(left,right):
res = []
while len(left) > 0 and len(right) > 0:
if left[0] < right[0]:
res.append(left.pop(0))
else:
res.append(right.pop(0))
res += left
res += right
return res
nums = [3,6,19,15,4,100,368,34,56,78,89]
print(merge_sort(nums))
def xiersort(nums):
gap = len(nums) // 2
while gap > 0:
for i in range(gap,len(nums)):
current = nums[i]
while i-gap >= 0 and current < nums[i-gap]:
nums[i] = nums[i-gap]
i -= gap
nums[i] = current
gap //= 2
return nums
nums = [3,6,19,15,4,100,368,34,56,78,89]
print(xiersort(nums))
1、Python算法图解
2、https://facert.gitbooks.io/python-data-structure-cn/5.%E6%8E%92%E5%BA%8F%E5%92%8C%E6%90%9C%E7%B4%A2/5.4.%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE/
如果觉得我的文章对您有用,请随意打赏。你的支持将鼓励我继续创作!