n=int(input("Nhập số phần tử trong danh sách: "))
a=[]
for i in range(n):
    b=int(input(f'Nhập số thứ {i+1}: '))
    a.append(b)
def LinearSearch():
    k=int(input("Nhập số cần tìm: "))
    vitri=[]
    for i in range(n):
        if a[i] == k:
            vitri.append(i+1)
    return vitri
def BinarySearch():
    k = int(input("Nhập số cần tìm: "))
    vitriq = []
    left = 0
    right= len(a) - 1
    while left <= right:
        mid = (left + right)//2
        if a[mid] == k:
            return mid
        elif a[mid] < k:
            left = mid + 1
        else:
            right = mid -1
    return -1
def InsertionSort(arr):
    for i in range(1,len(arr)):
        value = a[i]
        j=i-1
        while j>=0 and a[j] > value:
            a[j+1] = a[j]
            j=j-1
        a[j+1] = value
    return arr
def SelectionSort(arr):
    for i in range(len(arr)-1):
        iMin=i
        for j in range(i+1,len(arr)):
            if arr[j] < a[iMin]:
                iMin=j
        arr[i],arr[iMin]=arr[iMin],arr[i]
    return arr
def BubbleSort(arr):
    for i in range(len(arr)-1):
        for j in range(len(arr)-1-i):
            if arr[j] > arr[j+1]:
                arr[j],arr[j+1]=arr[j+1],a[j]
    return arr
print("""===MENU===
1.Tìm kiếm tuần tự
2.Tìm kiếm nhị phân
3.Thuật toán chèn
4.Thuật toán chọn
5.Thuật toán nổi bọt
0.Thoát""")
h=int(input("Nhập lựa chọn: "))
if h == 1:
   timkiemtt = LinearSearch()
   if len(timkiemtt) > 0:
       print("Số cần tìm ở vị trí", *timkiemtt)
   else:
       print("Không có số cần tìm")
elif h == 2:
    timkiemnp= BinarySearch()
    if timkiemnp != -1:
        print("Số cần tìm ở vị trí", timkiemnp+1)
    else:
       print("Không có số cần tìm")
elif h == 3:
    b= InsertionSort(a)
    print(f'Danh sách đã sắp xếp: {b}')
elif h == 4:
    o = SelectionSort(a)
    print(f'Danh sách đã sắp xếp: {o}')
elif h == 5:
    m = BubbleSort(a)
    print(f'Danh sách đã sắp xếp: {m}')
elif h == 0:
    exit()