Binary Search tìm kiếm trên dãy có thứ tự nên các phần tử bằng nhau sẽ nằm liền kề nhau. Do đó, sau khi tìm được vị trí phần tử thỏa điều kiện, từ vị trí đó xét tiếp các phần tử nằm bên trái và bên phải của nó. Ngoài ra, có thể dùng Binary Search 2 lần để tìm vị trí phần tử đầu tiên không nhỏ hơn KEY và vị trí phần tử đầu tiên lớn hơn KEY. Từ đó, suy ra đoạn phần tử có giá trị bằng KEY
Thuật toán Tìm kiếm nhị phân vẫn có thể hoạt động khi dãy số có phần tử trùng nhau. Tuy nhiên, thuật toán chỉ trả một vị trí mid mà tại đó a[mid] = x (khóa tìm kiếm). Nếu muốn tìm tất cả phần tử trùng lặp thì cần phải duyệt thêm sang bên trái và bên phải của vị trí mid.
cảm ơn thầy nhiều , bài giảng rất hay
em rất ít cmt nhưng thầy giảng dễ hiểu và rõ ràng quá, cảm ơn thầy, chúc thầy nhiều sức khỏe.
bài giảng tuyệt vời ! , cảm ơn thầy vì đã chia sẻ kiến thức hữu ích này ạ
Bài giảng rất dễ hiểu, cảm ơn anh Thầy nhiều ạ
rất dễ hiểu ạ. em cảm ơn ạ!!
Phần code của thầy hình như viết nhầm chỗ xét điều kiện đúng k ạ.
Phải là: If(a[mid] == x) return mid;
Chỗ đó slide viết nhầm nhé! Chỉnh sửa lại là if(a[mid] == x) return mid;
thầy ơi ở bài vận dụng đầu tiên số 5 ở vị trí số 4 nhưng thuật toán lại ra vị trí số 3 là sao ạ?
mong thầy trả lời.
Trong ngôn ngữ lập trình C#, các phần tử của mảng được đánh chỉ số bắt đầu từ 0 (số 5 là phần tử thứ 4 trong mảng nên có chỉ số là 3)
a cho em hỏi là nếu tìm kiếm x=7 mà có hai giá trị 7 thì làm như thế nào ạ. Em cảm ơn a
Binary Search tìm kiếm trên dãy có thứ tự nên các phần tử bằng nhau sẽ nằm liền kề nhau. Do đó, sau khi tìm được vị trí phần tử thỏa điều kiện, từ vị trí đó xét tiếp các phần tử nằm bên trái và bên phải của nó. Ngoài ra, có thể dùng Binary Search 2 lần để tìm vị trí phần tử đầu tiên không nhỏ hơn KEY và vị trí phần tử đầu tiên lớn hơn KEY. Từ đó, suy ra đoạn phần tử có giá trị bằng KEY
hay quá ạ
Dạ em xin chào thầy ạ, thầy có thể ra 1 list về cấu trúc dữ liệu và giải thuật được không ạ? Thầy giảng rất hay ạ
Hay quá ạ
anh ơi, em tìm hiểu thấy nói là không nên áp dụng thuật toán tìm kiếm nhị phân khi dãy có phần tử trùng nhau. tại sao ạ
Thuật toán Tìm kiếm nhị phân vẫn có thể hoạt động khi dãy số có phần tử trùng nhau. Tuy nhiên, thuật toán chỉ trả một vị trí mid mà tại đó a[mid] = x (khóa tìm kiếm). Nếu muốn tìm tất cả phần tử trùng lặp thì cần phải duyệt thêm sang bên trái và bên phải của vị trí mid.
@@lochuynh1401 Dạ, em cảm ơn ạ
có thể cho e xin pp của bài giảng này dc k ak? cảm ơn anh
biến a[i] ở đâu v, a[mid] chứ
hay quá ạ