Tìm kiếm

Tìm kiếm

Tìm kiếm luôn là một bài toán quan trọng, hầu hết trong hoạt động của người dùng

Phát biểu bài toán

  1. INPUT: Dãy n đối tượng r1,r2,...,rn. Mỗi đối tượng ứng với khóa ki (0<=i<=n). Giá trị X cần tìm
  2. OUTPUT: vị trí của X trong dãy đối tượng(khóa ki)

Để đơn giản, ta xem mỗi đối tượng là một số trong dãy số n phần tử

  1. Input: Mảng A[n], giá trị X
  2. Output: Vị trí i của X trong mảng

Có 2 thuật toán chính dùng để tìm kiếm

  1. Tìm kiếm tuyến tính(tìm từ đầu tới cuối). Độ phức tạp O(n)
  2. Tìm kiếm nhị phân(Chia nhỏ dần). Độ phức tạp:O(log(n))

Ngoài ra còn vài thuật toán: Tìm kiếm nội suy( khá giống tìm kiếm nhị phân), Tìm kiếm Fibonacy Search( dựa trên dãy số Fibonacy)

1. Đầu tiên là tìm kiếm tuyến tính:

            int Sequential_Search(int A[],int n,int x){
                for(int i=0; i < n ; i++){
                    if(A[i]==x)
                    return i;
                }
                return -1;
            }

2. Tìm kiếm nhị phân - chỉ áp dụng trong mảng phần tử đã sắp xếp

Ý tưởng: Lấy một phần tử ở chính giữa làm gốc: A[mid], Mảng phần tử chia làm 2 phần [0,mid]; [mid+1,n-1]. Lúc này sẽ có 3 trường hợp:

  1. Nếu X=A[mid] thì mid chính là vị trí cần tìm.
  2. X nằm bên trái A[mid] thì ta tìm trong mảng phía bên trái [0,mid]
  3. X nằm bên phải A[mid] thì ta tìm trong mảng phía bên phải [mid+1,n-1]

Lặp lại cho đến khi Cận dưới > Cận trên của dãy 

        int Binary-Search( int A[], int n, int x) {//tìm vị trí của x trong dãy A[]
            int low = 0;//cận dưới của dãy khóa
            int hight = n-1;//cận trên của dãy khóa
            int mid = (low+hight)/2; //phần tử ở giữa
            while ( low <=hight) { //lặp trong khi cận dưới vẫn nhỏ hơn cận trên
                if ( x > A[mid] ) //nếu x lớn hơn phần tử ở giữa
                    low = mid + 1; //cận dưới được đặt lên vị trí mid +1
                else if ( x < A[i] )
                    hight = mid -1;//cận trên lùi về vị trí mid-1
                else
                    return(mide); //đây chính là vị trí của x
                mid = (low + hight)/2; //xác định lại phần tử ở giữa
            }
            return(-1); //không thấy x trong dãy khóa A.
            }