[Chia để trị] Tìm kiếm nhị phân

nhatlonggunz · July 30, 2016, 10:19am

Mở loạt bài về giải thuật (thật sự thì trình em gà, học được gì share cái đó thôi), em nghĩ em sẽ bắt đầu trước từ thuật toán chia để trị (devide to conquer).

Về thuật toán chia để trị:

Ở đây, chắc mọi người đã quá quen với tìm kiếm nhị phân (binary search), và theo mình nghĩ (hướng dẫn thì cứ xưng như thế), mọi người thường dùng vòng lặp phải không (không phải cũng cứ coi như phải đi cho mình vui ) ? Vậy thì giờ đổi gió xíu nhé.

Ý tưởng: Ta sẽ tìm xem giá trị cần tìm có nằm trong mảng không, nếu có, trả về chỉ số (index) của phần tử đó, không thì trả về -1. Tạm gọi thằng cần tìm là key đi ha (@nhatlonggunz bắt đầu chém gió từ đây, đa số mọi người đều biết về tìm kiếm nhị phân nên bỏ qua phần ý tưởng này cũng được)

Đầu tiên ta xét thằng ở giữa (mid) xem có giống cái key không.

Giống thì trả về thằng ở giữa, coi như chìa khóa đã tìm được lỗ… nhầm, ổ khóa
Không giống thì sẽ có 2 trường hợp.
1. Trường hợp cái chìa to hơn cái lỗ mid (key lớn hơn thằng ở mid), thì mình sẽ tìm những cái lỗ to hơn cái lỗ ở giữa (mid + 1 … cái lỗ to nhất có thể có)
2. Trường hợp cái chìa bé hơn cái lỗ (key < thằng ở mid) thì tìm những cái lỗ nhỏ hơn cái lỗ ở giữa (từ thằng nhỏ nhất có thể có… mid - 1)
Cứ lặp lại như thế
Rồi sẽ tới lúc, chỉ còn 1 cái lỗ duy nhất, ở đây sẽ có 2 trường hợp nữa

Cái lỗ vừa khít với cái chìa => Đó là cái lỗ cần tìm
Cái lỗ không vừa => Chết, hết lỗ khóa rồi => Không có cái lỗ nào vừa với cái chìa. trả về -1)

Đưa về một chút cho hợp với đệ quy, ở đây không cách vào được nên viết mô tả (mã giã, pseudocode hay gì cũng được) hơi khó, thôi bỏ qua luôn đi. Nói chung là dùng đệ quy :v base case là khi mảng không còn phần tử nào (đầu mảng > cuối mảng)

CODE
------------------------------C++----------------------------------

int binarySearch(int A[], int key, int left, int right)
{
    if(left > right) // Đầu lớn hơn cuối => mảng không còn cái lỗ nào để cắm chìa vào nữa
        return -1; // => trả về -1

    else{

        int mid = (left + right) / 2;

        if(A[mid] == key) // Kiểm tra thằng ở giữa
            return mid;

        if(A[mid] > key) // Khi cái chìa nhỏ hơn cái lỗ
            return binarySearch(A, key, left, mid - 1);

        if(A[mid] < key) // khi cái chìa lớn hơn cái lỗ
            return binarySearch(A, key, mid + 1, right);
        }
}

Tìm kiếm nhị phân thường thì nên dùng vòng lặp
CODE
------------------------------C++----------------------------------

int binarySearch(int A[], int key, int left, int right)
{
    int mid;

    while(l < r) // Tìm đến khi chỉ còn 1 số duy nhất
    {
        mid = (l + r) / 2;

        if(A[mid] == key)
            break;
        else if(A[mid] > key)    // Khi cái Key nằm bên trái thằng mid
            r = mid - 1;
        else                     // Khi cái key năm bên phải
            l = mid + 1;
    }

    if(a[l] == key) return l;   // Nếu tìm được Key
    else -1;                    // Nếu như Key không tồn tại trong mảng
}

Em làm mấy bài cơ bản, mọi người gop ý

Gio · April 25, 2015, 5:50pm

OK rồi. Tìm hiểu thêm hàm lower_bound và upper_bound nữa. nó cũng là Tìm kiếm nhị phân nhưng trả về vị trí đầu và cuối của key. Có thể trả về số phần tử = key = upper_bound(a,a+n,key)-lower_bound(a,a+n,key);

sufuijk · April 27, 2015, 6:41am

thờng thì tại mấy anh này làm biếng nên toàn dùng cái cơ bản cho mau dạng như test với 1 mô hình nhỏ thôi nhưng thật ra cách cơ bản thích hợp hơn với dạng test vì cách mà bạn nói thì phải sắp xếp mảng nữa rùi mới tiếp kiếm trong khi đó với cách cơ bản chỉ 3 4 dòng , mình cũng đồng ý là nó nhanh hơn vì loại nhìu phần tử k nhưng có lẻ đối với google hay mấy web lớn chương trình lớn mới dùng cách đó để tăng hiệu quá tìm kiếm còn mấy dạng như test thôi thì dùng cơ bản cho tiện

nguyenchiemminhvu · April 27, 2015, 7:10am

Chỉ thêm 2 dòng

#include <algorithm>
...
std::sort(...,...,...);

có gì đâu mà dài dòng.

nhatlonggunz · April 27, 2015, 7:38am

Mình đang làm về thuật toán chia để trị, mà bài này là cơ bản của thuật toán đó nên mình mới lấy làm ví dụ thôi nha.

Chứ theo mình thấy, dùng vòng lặp nhanh hơn cái này.

vtmyeuthuong · May 1, 2016, 5:37am

anh có thể giải thích rõ hơn về cách dùng hàm sort không ạ? em search trên mạng thì hàm sort là sort(begin, end) và nó sắp xếp tăng dần, thế giảm dần thì dùng như nào ạ? ^^

VanKhoa · May 1, 2016, 6:18am

Giảm dần thì có cái reverse(my_vector.begin(), my_vector.end())

superthin · May 2, 2016, 12:41pm

Mình thắc mắc là con người/ não của mình tìm kiếm mặc định theo thuật toán nào. Ví dụ như trên bàn bày ra một đống thẻ có đánh số và người ta đảo mắt một lát rồi lôi ra được thẻ có số lớn nhất/ nhỏ nhất. Thì đó là tìm kiếm gì?

Làm cách nào để máy tính tìm kiếm theo cách của con người? Ví dụ như đưa ra một bảng có khoảng vài chục con thú khác nhau, hỏi con nào là con mèo, người nhận ra phát một nhưng máy tính tìm thì quá rắc rối?

drgnz · May 2, 2016, 1:37pm

Hình như cái đó gọi là Visual Search đó a Võ Thin

TheSky · May 2, 2016, 1:49pm

Em nghĩ là cũng lần lượt nhưng không cố định từ đâu về đâu
Có thế đầu về cuối hoặc cuối về đầu. Có chăng thì giữa về hai bên
Nhưng đó là với đống thẻ số lượng ít trong tầm mắt ta.
Giả sử có một cái số lượng thẻ lớn vài mét. Khi đó vượt khỏi tầm mắt, thì ta cũng lại phải chạy lần lượt đi kiểm tra chứ cũng không sao mà đảo mắt một phát là ra ngay được

Tương tự vì cái bảng đó ít nên chúng ta cũng nhìn là ra luôn. Sẵn tiềm thức biết con mèo là gì rồi

Tóm lại theo em, não chúng ta cũng thực hiện tuần tự
Với lượng ít thì vô cùng nhanh.
Còn số lượng nhiều thì do lười nên việc tìm kiếm chậm trễ

hieuqt · May 2, 2016, 5:55pm

đệ quy evevy where :3

Khai_Nguyen_Quang1 · December 12, 2017, 3:37am

nhatlonggunz:
if(a[l] == key) return l; // Nếu tìm được Key
else -1; // Nếu như Key không tồn tại trong mảng

giải thích mình đoạn này đk k? mình chưa hiểu lắm.

rogp10 · December 12, 2017, 4:08am

Câu cuối thiếu return mà hai câu này là xong rồi

hoanghuysd · May 9, 2018, 7:20pm

+Đoạn đầu khai báo A[] nhưng bên dưới xài a[]

Đoạn cuối thiếu “return” -1
Code sau khi sửa:

int binarySearch(int A[], int key, int l, int r)
{
int mid;

  while(l < r)
  {
      mid = (l + r) / 2;

      if(A[mid] == key)
      {
      	l = mid;
          break;
  	}

      else if(A[mid] > key)
          r = mid - 1;
      else
          l = mid + 1;
  }

  if(A[l] == key)
  {
  	return l;  
  }
  else return -1;

}

superthin · May 10, 2018, 7:13am

Còn trường hợp ví dụ ai đó hỏi mình một thông tin gì đó, và nó không quá đơn giản, nên sau vài giây suy nghĩ, mình nói ra, đó là tìm kiếm gì nhỉ? Có thuật toán nào gọi là “tìm kiếm ngẫu nhiên” không?

[Chia để trị] Tìm kiếm nhị phân

nhatlonggunz: if(a[l] == key) return l; // Nếu tìm được Key else -1; // Nếu như Key không tồn tại trong mảng

nhatlonggunz:
if(a[l] == key) return l; // Nếu tìm được Key
else -1; // Nếu như Key không tồn tại trong mảng