關于算法的兩個例子

算法例子一:給定一個清單和一個整數,找到兩個數的下标,使得這兩個數的各為給定的整數,保證肯定僅有一個結果

窮舉法:

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)