排序與搜尋

a = [5, 1, 3, 6, 3, 4, 8, 2, 1]
b = sorted(a)   # 不改 a
a.sort()        # 改 a

sorted(a) 是在不改變 a 的情況下回傳 a 排序後的 list

寫排序規則

a.sort(key=lambda x: x[1])

上述指令的意思是排序用的 key 值是對於每一個元素 x(自己隨便取名字)，取出 x[1]當作比較對象。當
然可以用各種欄位運算的結果來排序，例如：

a.sort(key=lambda x: x[1]+x[0])

例如：

a = [[1,3], [2,1], [2,4], [2,6]]
a.sort(key=lambda x : x[0] + x[1])
print(a) # [[2, 1], [1, 3], [2, 4], [2, 6]]

也可以由大排到小

a = [[1, 3], [2, 1], [2, 4], [2, 6]]
a.sort(key=lambda x: x[0] + x[1], reverse=True)
print(a) # [[2, 6], [2, 4], [1, 3], [2, 1]]

cmp(a, b) 回傳規則

Python 的 cmp 回傳和 C++ 不一樣，C++ 裡面 cmp(a, b) 回傳 true，代表 a 應該排在 b 前面。

而 Python 是像下面這樣。

def cmp(a, b):
    return 負數   # a 排在 b 前面
    return 0      # a 和 b 順序相同
    return 正數   # a 排在 b 後面

可以記成：

回傳值	意思
< 0	a 在前(左)
0	一樣(不動)
> 0	b 在前(左)

Danger | 注意

return 0 盡量要寫。
然後 reutrn 0 有時候放最後面就好

會這樣是因為最基本的由小到大寫法是：

from functools import functools

def cmp(a, b):
    return a - b

arr = [5, 2, 9, 1]
arr.sort(key=cmp_to_key(cmp))

print(arr)

所以負數是代表 a 在前面。

範例：

from functools import cmp_to_key

def cmp(a, b):      # 依照前面的排序
    if a[0] < b[0]:
        return -1
    elif a[0] > b[0]:
        return 1
    
    return 0 # 放最後面

points = [(1, 3), (5, 2), (9, 1), (2, 5)]
points.sort(key=cmp_to_key(cmp))

print(points) # [(1, 3), (2, 5), (5, 2), (9, 1)]

線性搜尋

在沒有順序的資料中搜尋只能一個一個慢慢找

a = [5, 1, 3, 4, 1, 8, 2, 3, 3, 7]
x = 6

for i in range(len(a)):
    if a[i] == x:
        break

print('end with i =', i)

if a[i] == x:
    print(x, 'found at', i)
else:
    print(x, 'not found')

---

如果只要知道在或不在，可以用 in 來檢查。

if x in a:
    print('yes')
else:
    print('no')

---

如果確定 x 在 a 中，可以用內建函數 index 來找位置。

i = a.index(3)      # 可以找到第一個 3 的位置
i = a.index(3, i+1) # i+1 開始找

---

list.index(x) 在 x 不存在時會引發錯誤，所以使用上要小心。

Python 可以用錯誤處理的方式做，但初學者不太容易使用，可以用 in 搭配 index 來做。

a = [5, 1, 3, 4, 1, 8, 2, 3, 3, 7]
x = 9

if x in a:
    print('yes, found at', a.index(x))
else:
    print('no')

二分搜尋的 lower_bound / upper_bound

import bisect # 或是寫 from bisect import bisect_left, bisect_right

a = [1, 4, 5, 6, 6, 6, 7, 9, 10]
i = bisect.bisect_left(a, 6)        # lower_bound
print(i)
i = bisect.bisect_right(a, 6)       # upper_bound
print(i)