算法例子一:给定一个列表和一个整数,找到两个数的下标,使得这两个数的各为给定的整数,保证肯定仅有一个结果
穷举法:
def brute_force(li,target):
n=len(li)
for i in range(0,n):
for j in range(i+1,n):
if li[i]+li[j]==target:
return i,j二分查找法:
def bin_search(li, val):
low = 0
high = len(li) - 1
while low <= high:
mid = (low + high) // 2
if li[mid] == val:
return mid
elif li[mid] > val:
high = mid - 1
else:
low = mid + 1
return None
def search_index(li, target):
li.sort()
for i in range(0, len(i)):
j=bin_search(li[i + 1:], target - li[i])
if j:
return i,j方法三
先给列表排序,然后循环遍历列表,如果列表第一个数与列表最后一个数相加的和大于target,把被加数向左偏移一位,
如果列表第一个数与列表最后一个数相加的和小于target,把加数向右偏移一位
如果列表中两个数相加等于target,则返回列表中的两个数的下标
def search_index(li,target):
li.sort()
j=len(li)-1
for i in range(j):
if li[i] + li[j] < target:
i += 1
elif li[i] + li[j] > target:
j -=1
else:
return i,j算法例子二:给定一个升序列表和一个整数,返回该整数在列表中的下标范围
思路:先使用二分法找到val在列表中的下标,然后把下标分别向左和向中移动,直到下标的值不等于目标整数时返回下标的元组
def bin_search(li,val):
low=0
high=len(li)-1
while low <= high:
mid=(low + high) // 2
if li[mid] == val:
return mid
elif li[mid] > val:
high = mid -1
else:
low=mid + 1
return None
def search_index(li,val):
i=0
j=0
mid=bin_search(li,val)
i=mid-1
j=mid + 1
while li[i] ==val:
i -= 1
while li[j] == val:
j += 1
return (i+1,j-1)
