1. Đặt vấn đề:

Giả sử chúng ta có một mảng M gồm N phần tử. Vấn đề đặt ra là có hay không phần tử có giá trị bằng X trong mảng M? Nếu có thì phần tử có giá trị bằng X là phần tử thứ mấy trong mảng M? Để giải quyết vấn đề này, chúng ta sẽ đi tìm hiểu 2 giải thuật "Linear Search" và "Binary Search".

2. Giải thuật tìm kiếm tuần tự (Linear Search)

• Tư tưởng: Lần lượt so sánh các phần tử của mảng M với giá trị X bắt đầu từ phần tử đầu tiên cho đến khi tìm đến được phần tử có giá trị X hoặc đã duyệt qua hết tất cả các phần tử của mảng M thì kết thúc.
• Thuật toán

B1: k = 1 //Duyệt từ đầu mảng
B2: IF M[k] !=X AND k = N //Nếu chưa tìm thấy và cũng chưa duyệt hết mảng
    B2.1: k++ 
    B2.2: Lặp lại B2 
B3: IF k = N 
    Tìm thấy tại vị trí k
B4: ELSE 
    Không tìm thấy phần tử có giá trị X
B5: Kết thúc

• Cài đặt thuật toán: Xây dựng 1 hàm tìm kiếm phần tử có giá trị X trên mảng M có N phần tử. Nếu tìm thấy, hàm trả về một số nguyên có giá trị 0 đến N-1 là vị trí tương ứng của phần tử tìm thấy. Trong trường hợp ngược lại, hàm trả về giá trị -1 (không tìm thấy).

int LinearSearch (T M[], int N, T X)

{ 

    int k = 0;

    while (M[k] != X && k < N)

        k++;

    if (k < N)

        return (k);

    return (-1);

}

• Cải tiến thuật toán: Trong thuật toán trên, ở mỗi bước lặp chúng ta cần thực hiện 2 phép so sánh để kiểm tra và kiểm soát hết mảng. Chúng ta có thể giảm bớt 1 phép so sánh nếu chúng ta thêm vào cuối mảng một phần tử cầm canh có giá trị bằng X để nhận diện ra sự hết mảng khi duyệt mảng, khi đó thuật toán được cải tiến sau:

B1: k = 1 
B2: M[N+1] = X //Phần tử cầm canh
B3: IF M[k] ≠ X 
    B3.1: k++ 
    B3.2: Lặp lại B3 
B4: IF k < N 
    Tìm thấy tại vị trí k 
B5: ELSE //k = N đây chỉ là phần tử cầm canh
    Không tìm thấy phần tử có giá trị X
B6: Kết thúc

• Cài đặt thuật toán cải tiến:

int LinearSearch1(T M[], int N, T X)

{

    int k = 0;

    M[N] = X;

    while (M[k] != X)

        k++;

    if (k < N)

        return (k);

    return (-1);

}

3. Giải thuật tìm kiếm nhị phân(Binary Search)

Với tập dữ liệu lớn thì Linear Search không hiệu quả, nên giải pháp là sử phương pháp tìm kiếm nhị phân sẽ hiệu quả hơn, tuy nhiên dữ liệu phải được sắp xếp theo thứ tự tăng dần trước khi tìm.

• Tư tưởng
  • Phạm vi tìm kiếm từ đầu First = 1 đến cuối của dãy Last = N
  • So sánh X với phần tử đứng giữa của dãy M là M[mid]
  • Nếu X= M[mid] -> tìm thấy
  • Nếu X< M[mid] -> rút ngắn phạm vi tìm về nửa đầu của dãy để tìm lúc này Last=mid-1
  • Nếu X> M[mid] -> rút ngắn phạm vi tìm về nửa cuối của dãy để tìm lúc này First=mid+1
  • Lặp lại quá trình cho đến khi tìm thấy X hoặc phạm vi tìm không còn nữa (First>Last)
• Cài đặt bằng đệ quy

int RecBinarySearch(T M[], int First, int Last, T X)

{

    if (First > Last)

        return (-1);

    int Mid = (First + Last) / 2;

    if (X == M[Mid])

        return (Mid);

    if (X < M[Mid])

        return (RecBinarySearch(M, First, Mid – 1, X));

    else

        return (RecBinarySearch(M, Mid + 1, Last, X));

}

//=======================================================

int BinarySearch(T M[], int N, T X)

{

    return (RecBinarySearch(M, 0, N – 1, X));

}

• Cài đặt không sử dụng đệ quy

int NRecBinarySearch (T M[], int N, T X)

{ 

    int First = 0;

    int Last = N – 1;

    while (First <= Last)

    { 

        int Mid = (First + Last)/2;

        if (X == M[Mid])

            return(Mid);

        if (X < M[Mid])

            Last = Mid – 1;

        else

            First = Mid + 1;

    }

    return(-1);

}

4. Hình ảnh minh họa

Link tải tài liệu và bài tập thực hành: https://hanam88.com/kho-tai-lieu/61/134/mot-so-thao-tac-voi-mang-1-chieu-cau-truc-du-lieu-mang.html