การค้นหา (Searching)

def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i        # เจอ คืน index
    return -1               # ไม่เจอ

print(linear_search([4, 2, 7, 1, 9], 7))  # 2
print(linear_search([4, 2, 7, 1, 9], 5))  # -1

# Python มี in และ index() ให้ใช้อยู่แล้ว (ก็เป็น O(n))
print(7 in [4, 2, 7])       # True

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2   # ตำแหน่งกลาง
        if arr[mid] == target:
            return mid              # เจอ
        elif arr[mid] < target:
            left = mid + 1          # เป้าอยู่ครึ่งขวา
        else:
            right = mid - 1         # เป้าอยู่ครึ่งซ้าย
    return -1

print(binary_search([1, 3, 5, 7, 9, 11], 7))   # 3
print(binary_search([1, 3, 5, 7, 9, 11], 4))   # -1