This web page requires JavaScript to be enabled.

JavaScript is an object-oriented computer programming language commonly used to create interactive effects within web browsers.

How to enable JavaScript?

Các thuật toán tìm kiếm [C]

10cth1-2 March 6, 2012 Nam Le 0

Tìm kiếm tuyến tính:

Ý tưởng là duyệt tuần tự bắt đầu từ phần tử đầu tiên, lần lượt so sánh với key tương ứng cho đến khi gặp phần tử cần tìm hoặc đi hết dãy. Giá trị trả về là vị trí xuất hiện đầu tiên của key trong dãy, nếu ko có thì trả về -1.

Giải thuật tìm kiếm tuyến tính không phụ thuộc vào thứ tự của các phần tử trong mảng, do vậy đây là phương pháp tổng quát nhất để tìm kiếm trên một dãy bất kỳ.

[codes=c]int timtuyentinh(int a[],int n, int key)  
{  
  for(int i=0; i  {  
    if(a[i]==key)  
        return i;  
  }  
  return -1;  
} [/codes]

Tìm kiếm nhị phân:

Áp dụng khi dãy đã được sắp xếp, ý tưởng chính là chia đôi dãy ra để tìm.

Thuật giải nhị phân dựa vào quan hệ giá trị của các phần tử trong mảng để định hướng trong quá trình tìm kiếm, do vậy chỉ áp dụng được với dãy đã có thứ tự.

Thuật giải nhị phân tìm kiếm nhanh hơn tìm kiếm tuyến tính. Tuy nhiên khi áp dụng thuật giải nhị phân thì cần phải quan tâm đến chi phí cho việc sắp xếp mảng. Vì khi mảng được sắp thứ tự rồi thì mới tìm kiếm nhị phân.

[codes=c]int BinarySearch(int a[], int n, int key){
  int left = 0, right = n-1, mid;
  while (left <= right){
    mid = (left + right)/ 2;  // lấy điểm giữa
    if (a[mid] == key)  // nếu tìm được
      return mid;
    if (a[mid] < key)    // tìm đoạn bên phải mid
      left = mid+1;    
    else
      right = mid-1;  // tìm đoạn bên trái mid
  }
  return -1;      // không tìm được
}[/codes]


Last modified on December 9th, 2020 at 12:57 am

Nam Le
lequocnam



0 responds

Leave a Reply

Your email address will not be published. Required fields are marked *