Tìm tuyến tính so với tìm nhị phân
Tìm tuyến tính so với tìm nhị phân
Chia đôi thì nhanh hơn quét, ai cũng biết. Nhưng tìm nhị phân đòi mảng phải sắp sẵn, mà sắp thì tốn tiền. Nếu bạn chỉ tìm một lần thì sắp trước là lỗ. Bài này tính ra chính xác mốc huề vốn.
Bạn có một mảng đã sắp và cần biết một giá trị có nằm trong đó hay không. Cách thật thà là quét từ đầu tới cuối. Cách khôn hơn là hỏi phần tử ở giữa: nếu nó nhỏ hơn giá trị cần tìm thì cả nửa trái vứt đi được, còn nếu lớn hơn thì nửa phải vứt đi được. Mỗi câu hỏi cắt đôi số ứng viên, nên thay vì n phép so sánh bạn chỉ mất khoảng log₂ n.
Câu chuyện đó đúng, và nó cũng là chỗ ba hiểu lầm hay xảy ra nhất. Thứ nhất, người ta hay nghĩ tìm nhị phân "luôn" mất đúng log₂ n bước, kể cả khi không tìm thấy. Không phải: đó là cái trần, và bài này sẽ cho bạn một phản ví dụ ngay ở trạng thái mở đầu. Thứ hai, khi tay trắng thì vòng lặp không hề tay trắng, nó đang giữ sẵn chỗ mà giá trị đó lẽ ra phải nằm, và hầu như không ai lấy. Thứ ba, và đây là chỗ đắt nhất: tìm nhị phân giả định mảng đã sắp, còn cái giả định đó không miễn phí. Nếu bạn chỉ hỏi một câu thì đi sắp cả mảng rồi mới hỏi là một quyết định tồi, và tồi một cách đo được.
Sim dưới đây chạy từng bước cả hai cách trên cùng một mảng, đếm phép so sánh thật của cả hai, vẽ khoảng đang xét của tìm nhị phân thu hẹp dần, rồi tính mốc hoà vốn. Mọi tham số đều sửa được. Nếu bạn thấy bài đang dẫn bạn tới một kết luận, hãy vặn núm cho tới khi kết luận đó sai.
1 · Mảng đã sắp và giá trị cần tìm ✎ sửa được
Mảng có 16 phần tử, chạy từ 10 tới 160, mỗi bước cách nhau 10. Giá trị cần tìm là 81, và nó không có trong mảng.
2 · Chạy từng bước cả hai cách
| bước | chỉ số | giá trị | so với 81 |
|---|---|---|---|
| 1 | 0 | 10 | nhỏ hơn |
| 2 | 1 | 20 | nhỏ hơn |
| 3 | 2 | 30 | nhỏ hơn |
| 4 | 3 | 40 | nhỏ hơn |
| 5 | 4 | 50 | nhỏ hơn |
| 6 | 5 | 60 | nhỏ hơn |
| 7 | 6 | 70 | nhỏ hơn |
| 8 | 7 | 80 | nhỏ hơn |
| 9 | 8 | 90 | lớn hơn |
| 10 | 9 | 100 | lớn hơn |
| 11 | 10 | 110 | lớn hơn |
| 12 | 11 | 120 | lớn hơn |
| … còn 4 bước nữa, bảng chỉ in 12 dòng đầu | |||
| 16 | 15 | 160 | lớn hơn |
| bước | khoảng | còn lại | giữa | giá trị | so với 81 |
|---|---|---|---|---|---|
| 1 | [0, 15] | 16 | 7 | 80 | nhỏ hơn |
| 2 | [8, 15] | 8 | 11 | 120 | lớn hơn |
| 3 | [8, 10] | 3 | 9 | 100 | lớn hơn |
| 4 | [8, 8] | 1 | 8 | 90 | lớn hơn |
3 · Ca không tìm thấy, và chỗ lẽ ra nó phải nằm
Không tìm thấy, nhưng vòng lặp không ra về tay trắng hoàn toàn. Biến low lúc dừng đang bằng 8, đúng là chỗ phải chèn 81 vào để mảng vẫn sắp. Đếm cách khác cũng ra chừng ấy: có 8 phần tử nhỏ hơn 81. Đây chính là thứ lower_bound trả về, và nó có sẵn mà hầu như không ai lấy. Chú ý con số bên trái so với cái trần bên cạnh nó: lần này tìm nhị phân dừng ở 4, tức ít hơn trần 5. Trần là chặn trên, không phải chi phí cố định.
4 · Bẫy tràn số của (low + high) / 2 ✎ sửa được
low + high nếu số nguyên không có giới hạn | 2.147.483.648 |
|---|---|
giới hạn của int 32 bit có dấu | 2.147.483.647 |
low + high sau khi máy 32 bit quấn vòng | -2.147.483.648 |
(low + high) / 2 trên máy đó | -1.073.741.824 |
low + (high - low) / 2 | 1.073.741.824 |
(low + high) >>> 1, cách vá của Java | 1.073.741.824 |
ArrayIndexOutOfBoundsException. Hai công thức bên dưới vẫn ra 1.073.741.824, đúng như phải thế.Vì low và high đều leo tới n - 1 trước khi vòng lặp bỏ cuộc, tổng lớn nhất một lần tìm có thể chạm là 2(n - 1). Đặt số đó lớn hơn 2.147.483.647 rồi giải ra: mảng 1.073.741.824 phần tử vẫn an toàn, mảng 1.073.741.825 phần tử thì không. Mảng đang vẽ có 16 phần tử nên còn xa lắm, và đó cũng là lý do bẫy này sống được lâu tới vậy.
5 · Sắp trước có đáng không ✎ sửa được
Sắp 16 phần tử tốn 49 phép so sánh, trả một lần. Sau đó mỗi lượt tìm rẻ hơn hẳn. Câu hỏi là phải tìm bao nhiêu lượt thì khoản trả trước đó mới huề vốn.
| với 3 lượt tìm | sắp trước rồi tìm nhị phân | quét tuyến tính mỗi lượt | ai thắng | hoà vốn từ lượt |
|---|---|---|---|---|
| theo ca đang chạy (16 và 4 mỗi lượt) | 61 | 48 | quét tuyến tính | 5 |
| theo trường hợp xấu nhất (16 và 5 mỗi lượt) | 64 | 48 | quét tuyến tính | 5 |
- Nó đếm phép so sánh, nó không đo giây. Trên mảng nhỏ thì quét tuyến tính thường nhanh hơn thật, dù thua đậm về số phép so sánh: nó đọc bộ nhớ liền một mạch nên bộ nhớ đệm của máy nạp trước được, còn tìm nhị phân nhảy lung tung nên gần như lần nào cũng phải đợi. Muốn biết cái nào nhanh hơn thì phải đo, không suy ra từ đây được.
- Một phép so sánh ở đây là một lần đối chiếu ba chiều với một phần tử: nhỏ hơn, bằng, hay lớn hơn. Code C++ hay Java thường viết thành hai phép so sánh hai chiều mỗi vòng, tức nhân đôi con số của tìm nhị phân. Đó là quy ước chứ không phải chân lý, và đổi quy ước thì mốc hoà vốn dịch theo.
- Ba chi phí sắp xếp đều là công thức trường hợp xấu nhất, không phải số đo. Sắp xếp thật còn tuỳ dữ liệu đã gần sắp sẵn hay chưa, còn tuỳ cài đặt, và thư viện chuẩn thường nhanh hơn công thức ở đây.
- Chuyện thư viện chuẩn Java dính lỗi tràn số suốt chín năm là một sự kiện lịch sử có nguồn ghi ngay trên. Cổng kiểm số của bài canh phần số học 32 bit, nó không canh và không thể canh được câu chuyện đó.
Ở trạng thái mở đầu, sim đang nói gì
Mảng có 16 phần tử, chạy từ 10 tới 160, mỗi bước cách nhau 10. Giá trị cần tìm là 81, và nó không có trong mảng: nó lọt đúng vào khe giữa 80 và 90.
Quét tuyến tính mất 16 phép so sánh. Nó phải sờ vào từng phần tử một, và chỉ khi sờ hết mới dám kết luận là không có. Đây là điểm đối xứng quan trọng nhất của bài: với quét tuyến tính, không tìm thấy chính là trường hợp xấu nhất, mà lại là trường hợp rất hay gặp trong đời thật.
Tìm nhị phân mất 4 phép so sánh. Nó đi thế này, bạn đối chiếu với bảng các bước trong sim:
| bước | khoảng đang xét | còn lại | hỏi chỉ số | giá trị | so với 81 | khoảng mới |
|---|---|---|---|---|---|---|
| 1 | [0, 15] | 16 | 7 | 80 | nhỏ hơn | [8, 15] |
| 2 | [8, 15] | 8 | 11 | 120 | lớn hơn | [8, 10] |
| 3 | [8, 10] | 3 | 9 | 100 | lớn hơn | [8, 8] |
| 4 | [8, 8] | 1 | 8 | 90 | lớn hơn | [8, 7], rỗng |
Số ứng viên đi 16 → 8 → 3 → 1 → 0. Nhìn cột đó là thấy hết bản chất: mỗi phép so sánh vứt đi khoảng một nửa những gì còn lại.
Ca không tìm thấy, và cái trần không phải là chi phí cố định
Trần của tìm nhị phân trên n phần tử là ⌊log₂ n⌋ + 1. Với n = 16 thì trần là 4 + 1 = 5. Nhưng lần tìm ở trên chỉ mất 4. Bốn khác năm, và đó không phải may mắn.
Đây là chỗ rất nhiều tài liệu nói ẩu, kể cả bản đặc tả mà bài này được giao. Câu nói ẩu là "tìm nhị phân trên mảng n phần tử luôn dừng sau ⌊log₂ n⌋ + 1 bước dù có tìm thấy hay không". Cổng kiểm số của bài đã quét cạn mọi giá trị có thể tìm hụt, với mọi n từ 1 tới 200, và kết quả đo được là:
- Không lần tìm nào, trúng hay trượt, vượt quá
⌊log₂ n⌋ + 1. Cái trần là thật. - Với mỗi
n, cái trần đều có lần chạm tới. Nó là chặn chặt, không phải chặn lỏng. - Một lần tìm hụt luôn tốn
⌊log₂ n⌋hoặc⌊log₂ n⌋ + 1phép so sánh, không bao giờ ra ngoài hai giá trị đó. Nên chi phí tìm hụt chỉ dao động đúng một bước. - Nhưng giá trị nhỏ hơn thật sự xảy ra, nên chữ "luôn" là sai. Phản ví dụ nhỏ nhất là
n = 2: tìm một giá trị nhỏ hơn cả hai phần tử chỉ mất 1 phép so sánh, trong khi trần là 2.
Chữ "luôn" đúng ở đúng một họ: khi n = 2^k - 1, tức 1, 3, 7, 15, 31, 63. Lúc đó cây tìm kiếm đầy hoàn hảo, mọi chỗ trống đều nằm cùng một độ sâu, nên mọi lần tìm hụt đều tốn đúng bằng trần. Còn ngay khi n là luỹ thừa của 2, chẳng hạn 16 như trạng thái mở đầu, thì luôn tồn tại một lần tìm hụt về đích sớm hơn một bước. Bạn tự kiểm được: bấm ca không có, nhỏ hơn mọi phần tử rồi so con số với ca không có, lớn hơn mọi phần tử.
Điều thật sự đáng nhớ ở đây không phải mấy con số lệch nhau một bước. Nó là chuyện này: với tìm nhị phân, tìm hụt không hề đắt hơn tìm trúng. Cổng đã kiểm cả mệnh đề đó, và lần tìm hụt tệ nhất chưa bao giờ tốn hơn lần tìm trúng tệ nhất, với mọi n từ 1 tới 120. Trong khi với quét tuyến tính, tìm hụt luôn là đúng trường hợp xấu nhất. Nếu dữ liệu của bạn có nhiều truy vấn trượt, khoảng cách giữa hai cách còn giãn ra nữa.
Bên cạnh đó, quét tuyến tính trên mảng đã sắp có thể khôn hơn một chút: gặp phần tử lớn hơn giá trị cần tìm thì dừng luôn, vì phía sau chỉ càng lớn. Bật công tắc dừng sớm trong sim, con số 16 tụt xuống 9. Vẫn thua 4 khá xa, nhưng đó là một cải tiến thật và miễn phí. Con số 9 cũng không ngẫu nhiên: nó bằng vị trí chèn cộng 1. Đẳng thức mà cổng khoá trên mọi mảng nó quét là bản đầy đủ, tức số nhỏ hơn giữa vị trí chèn cộng 1 và n: khi giá trị cần tìm lớn hơn mọi phần tử thì không có ô nào để mà dừng sớm, nên quét vẫn phải đi hết mảng.
Vị trí chèn: món quà không ai nhận
Khi tìm nhị phân kết thúc mà không thấy gì, biến low đang giữ giá trị 8. Đó chính là chỗ phải chèn 81 vào để mảng vẫn còn sắp. Đếm cách khác cũng ra chừng ấy: có đúng 8 phần tử nhỏ hơn 81, là 10 tới 80.
Đây không phải trùng hợp. Vòng lặp chỉ dừng khi low > high, và mọi phần tử ở bên trái low đều đã được chứng minh là nhỏ hơn giá trị cần tìm, còn mọi phần tử từ low trở đi đều đã được chứng minh là không nhỏ hơn. Đó đúng là định nghĩa của vị trí chèn. Trong thư viện chuẩn C++ hàm này tên là lower_bound, trong Java thì Arrays.binarySearch trả về -(vị trí chèn) - 1 khi không tìm thấy, chính là để bạn lấy được con số này thay vì chỉ nhận một chữ "không có".
Vì sao nó đáng giá? Vì nó biến một câu trả lời có hay không thành một câu trả lời có toạ độ. Nó cho bạn chèn phần tử mới vào đúng chỗ, cho bạn cắt lát "mọi phần tử trong khoảng từ a tới b" bằng hai lần tìm, cho bạn tìm phần tử gần nhất. Cổng kiểm số của bài khoá điều này rất chặt: trên toàn bộ lưới cấu hình, vị trí chèn mà vòng lặp trả về luôn khớp với phép đếm số phần tử nhỏ hơn, và chèn giá trị vào đúng chỗ đó thì mảng thu được vẫn sắp. Hai đường đi khác nhau tới cùng một con số.
Cái bẫy kinh điển: (low + high) / 2
Công thức tìm phần tử giữa trông hiển nhiên tới mức không ai nhìn lại:
int mid = (low + high) / 2; // sai trên mảng rất lớn
int mid = low + (high - low) / 2; // đúng
Hai biểu thức đó bằng nhau về mặt toán học, cổng kiểm số đã chứng minh trên toàn bộ lưới chỉ số hợp lệ. Nhưng chúng không bằng nhau trên máy tính, vì int 32 bit có dấu chỉ chứa được tới 2.147.483.647. Biểu thức thứ nhất cộng trước, và cái tổng đó có thể vượt giới hạn ngay cả khi low và high mỗi cái đều là chỉ số hoàn toàn hợp lệ. Biểu thức thứ hai trừ trước, nên nó không bao giờ tạo ra số nào lớn hơn high.
Tràn ở đâu? Mở mục 4 của sim, hai ô đang để low = high = 1.073.741.824, tức 2³⁰:
low + high= 2.147.483.648, đúng một đơn vị quá giới hạn;- máy 32 bit quấn nó về -2.147.483.648;
- chia 2, cắt phần lẻ về phía 0, ra -1.073.741.824;
- rồi chương trình đi đọc
a[-1.073.741.824]. Trong C++ đó là hành vi không xác định, trong Java làArrayIndexOutOfBoundsException.
Còn low + (high - low) / 2 vẫn ra 1.073.741.824, đúng như phải thế. Cách vá thứ hai, kiểu Java, là (low + high) >>> 1: cộng cứ để nó tràn, rồi dịch phải theo kiểu không dấu, vì mẫu bit đã quấn kia đọc lại như số không dấu thì vẫn là tổng đúng. Cổng khoá rằng hai cách vá này cho cùng một chỉ số trên mọi cặp hợp lệ.
Mốc chính xác là bao nhiêu? Trong một lần tìm, low và high cùng leo tới n - 1 trước khi vòng lặp bỏ cuộc, nên tổng lớn nhất chạm được là 2(n - 1), và nó chạm thật chứ không phải chặn lỏng: cứ tìm một giá trị lớn hơn mọi phần tử thì sẽ đi qua trạng thái đó. Giải 2(n - 1) > 2.147.483.647 ra n ≥ 1.073.741.825. Vậy:
- mảng 1.073.741.824 phần tử, tức
2³⁰, vẫn an toàn: tổng tệ nhất là 2.147.483.646, còn thiếu một đơn vị nữa mới chạm; - mảng 1.073.741.825 phần tử, tức
2³⁰ + 1, thì hỏng: tổng tệ nhất là 2.147.483.648, quá đúng một đơn vị.
Cổng kiểm số khoá cả hai phía của mốc đó, vì một cái mốc chỉ được khẳng định ở một phía thì không phân biệt được > với ≥.
Cần nói rõ hai chuyện. Một là JavaScript không tràn kiểu này: số của nó là dấu chấm động 64 bit, chứa số nguyên chính xác tới 2⁵³, nên engine của sim này viết công thức nào cũng chạy đúng. Bẫy là bẫy thật của người viết C++ và Java, và của bất cứ ngôn ngữ nào có int cố định 32 bit. Sim mô phỏng lại phép quấn đó bằng số học chứ không phải gặp nó. Hai là mảng 2³⁰ + 1 phần tử kiểu int 4 byte nặng hơn 4 GiB, nên bẫy này hiếm. Nhưng nó có thật: Joshua Bloch công bố nó năm 2006, và lúc đó nó đã nằm trong java.util.Arrays.binarySearch của thư viện chuẩn Java suốt chín năm. Nguồn đầy đủ ghi ngay trong sim, kèm ngày chép. Cổng kiểm số canh phần số học 32 bit, nó không canh và không thể canh được câu chuyện lịch sử kia.
Mốc hoà vốn: chỗ hầu như không sách nào cho tính
Đây là phần quan trọng nhất của bài, và cũng là phần bị bỏ qua nhiều nhất.
Tìm nhị phân đòi mảng đã sắp. Nếu mảng chưa sắp thì bạn phải sắp, và sắp tốn tiền. Nên phép so sánh công bằng không phải là "n so với log n", mà là:
sắp trước rồi tìm: chi phí sắp + số lượt × chi phí mỗi lượt tìm nhị phân
quét tuyến tính: số lượt × chi phí mỗi lượt quét
Cột trái có một khoản trả trước. Cột phải thì không, nhưng mỗi lượt đắt hơn. Nên với ít lượt tìm, quét thắng, và nó thắng một cách rõ ràng chứ không sát nút.
Vặn núm số lần tìm trong sim mà xem. Ở trạng thái mở đầu số lượt đang là 3, và bảng đang nói:
| với 3 lượt tìm | sắp trước rồi tìm nhị phân | quét tuyến tính | ai thắng |
|---|---|---|---|
| theo ca đang chạy | 49 + 3 × 4 = 61 | 3 × 16 = 48 | quét tuyến tính |
| theo trường hợp xấu nhất | 49 + 3 × 5 = 64 | 3 × 16 = 48 | quét tuyến tính |
Sắp 16 phần tử bằng sắp xếp trộn tốn 49 phép so sánh trong trường hợp xấu nhất, theo công thức n⌈log₂n⌉ - 2^⌈log₂n⌉ + 1 = 16 × 4 - 16 + 1. Bốn mươi chín phép so sánh trả trước, để rồi tiết kiệm 11 phép mỗi lượt. Ba lượt tiết kiệm được 33, chưa bù nổi 49. Sắp trước đang lỗ 16 phép so sánh.
Vậy phải mấy lượt? Lấy chi phí sắp chia cho khoản tiết kiệm mỗi lượt, rồi lấy phần nguyên cộng 1:
tiết kiệm mỗi lượt = 16 - 5 = 11
mốc hoà vốn = ⌊49 / 11⌋ + 1 = 4 + 1 = 5
Kiểm cả hai phía, và đây đúng là chỗ cổng phải khoá chặt nhất:
- ở 4 lượt: sắp trước mất
49 + 4 × 5 = 69, quét mất4 × 16 = 64. Quét vẫn thắng. - ở 5 lượt: sắp trước mất
49 + 5 × 5 = 74, quét mất5 × 16 = 80. Bây giờ sắp trước mới thắng.
Chỗ dễ sai kinh khủng ở đây là viết ⌈49 / 11⌉ thay vì ⌊49 / 11⌋ + 1. Hai biểu thức đó chỉ khác nhau khi phép chia ra số nguyên chẵn, mà đúng lúc đó thì trần lại rơi vào lượt hoà, không phải lượt thắng. Cổng của bài chạy mốc hoà vốn theo hai đường độc lập, một là công thức đóng, hai là một phép dò đi từng lượt một cho tới khi cột trái rẻ hơn, rồi bắt hai đường phải khớp trên toàn lưới. Và nó khẳng định đúng tại mốc và đúng một bước dưới mốc, cả hai chiều.
Vặn thêm hai núm nữa để thấy mốc này nhạy tới đâu:
- Đổi cách tính chi phí sắp xếp sang sắp xếp chèn, tức
n(n-1)/2= 120 phép so sánh cho 16 phần tử. Mốc nhảy từ 5 lên 11. Sắp bằng thuật toán bậc hai thì phải hỏi nhiều gấp đôi mới huề vốn. - Kéo số phần tử lên 64. Sắp tốn 321 phép so sánh, mỗi lượt tiết kiệm
64 - 7 = 57, mốc là 6. Mảng lớn gấp bốn mà mốc chỉ nhích lên một. Đây mới là chỗ đáng nhớ: mốc hoà vốn lớn lên cỡlog n, chứ không lớn lên theon, vì chi phí sắp tăng nhưn log ncòn khoản tiết kiệm mỗi lượt tăng gần như tuyến tính. Hai con số sau tính bằng công thức chứ không kéo núm tới được, vì núm chặn ở 64: mảng 1.024 phần tử có mốc 10, mảng 1.048.576 phần tử có mốc 20. Nói cách khác, mảng to cỡ nào thì cũng chỉ cần vài chục lượt tìm là khoản trả trước đã hoàn vốn. Lưu ý mốc không đơn điệu tuyệt đối: nó nhích lên rồi có chỗ tụt lại một bước, nên đừng đọc nó như một hàm tăng đều. - Bấm ca ở đầu mảng. Quét chỉ mất 1 phép so sánh, còn tìm nhị phân mất 4. Bảng ghi thẳng không bao giờ: không có số lượt nào cứu nổi, vì mỗi lượt tìm nhị phân đã đắt hơn rồi. Đây là lời nhắc rằng "tuyến tính chậm hơn logarit" là một câu nói về trường hợp xấu nhất, không phải một lời hứa về mọi dữ liệu.
Và chuyện vị trí ảnh hưởng ra sao thì bấm lần lượt bốn ca là thấy ngay. Trên cùng mảng 16 phần tử: quét tuyến tính đi từ 1 phép so sánh khi giá trị ở đầu, lên 8 khi ở giữa, lên 16 khi ở cuối hoặc khi không có. Tìm nhị phân trong cả bốn ca chỉ dao động từ 1 tới 5. Một bên phụ thuộc hoàn toàn vào chỗ bạn may mắn đặt dữ liệu, bên kia gần như không.
Sim này đếm gì và không đếm gì
Phải nói thẳng trước khi bạn mang mấy con số này đi đâu.
Sim đếm phép so sánh, nó không đo giây. Đây không phải khiêm tốn khách sáo, nó là một khác biệt có thể lật ngược kết luận. Trên mảng nhỏ, quét tuyến tính thường nhanh hơn thật dù thua đậm về số phép so sánh, vì nó đọc bộ nhớ liền một mạch: bộ nhớ đệm của máy nạp sẵn cả một dải, và bộ nạp trước đoán được bước kế tiếp. Tìm nhị phân thì nhảy từ giữa sang một phần tư sang một phần tám, gần như lần nào cũng rơi vào dòng đệm khác, gần như lần nào cũng phải đợi. Một phép so sánh trong dãy liền mạch và một phép so sánh sau cú nhảy là hai thứ có giá khác hẳn nhau, mà sim này tính chúng bằng nhau. Muốn biết cái nào nhanh hơn trên máy của bạn thì phải đo, và đừng suy ra từ trang này.
Một phép so sánh ở đây là một lần đối chiếu ba chiều với một phần tử: nhỏ hơn, bằng, hay lớn hơn. Code C++ hay Java thường viết thành hai phép so sánh hai chiều mỗi vòng lặp, tức nhân đôi con số của tìm nhị phân. Đó là quy ước chứ không phải chân lý, và đổi quy ước thì mốc hoà vốn dịch theo.
Ba mô hình chi phí sắp xếp đều là công thức trường hợp xấu nhất, không phải số đo. Sắp xếp thật còn tuỳ dữ liệu đã gần sắp sẵn hay chưa, còn tuỳ cài đặt, và hàm sắp xếp trong thư viện chuẩn thường nhanh hơn công thức ở đây kha khá.
Muốn xem tại sao cách đếm phép tính lại đáng tin hơn cách bấm đồng hồ, đọc đếm phép tính. Muốn xem log n nằm ở đâu trong bảng xếp hạng các bậc tăng, đọc bậc tăng.
Tìm nhị phân đổi n phép so sánh lấy nhiều nhất ⌊log₂ n⌋ + 1, và cái ⌊log₂ n⌋ + 1 đó là trần chứ không phải chi phí cố định: một lần tìm hụt tốn ⌊log₂ n⌋ hoặc ⌊log₂ n⌋ + 1, chỉ dao động đúng một bước, và không bao giờ đắt hơn một lần tìm trúng. Khi tay trắng nó vẫn để lại vị trí chèn, thứ mà lower_bound trả về và ít ai lấy. Viết (low + high) / 2 thì tràn int 32 bit từ mảng 2³⁰ + 1 phần tử trở lên, viết low + (high - low) / 2 thì không, và đây là bẫy thật của người viết C++ và Java chứ không phải của JavaScript. Nhưng cái đáng nhớ nhất là chuyện tiền: tìm nhị phân đòi mảng đã sắp, nên nếu chỉ hỏi vài câu thì sắp trước là lỗ. Với mảng 16 phần tử và sắp xếp trộn, mốc huề vốn là 5 lượt tìm, và ở lượt thứ 4 thì quét tuyến tính vẫn còn thắng. Trước khi chọn thuật toán, hãy đếm xem bạn sẽ hỏi bao nhiêu câu.
- 1Mảng 16 phần tử đã sắp, bạn tìm một giá trị KHÔNG có trong mảng. Tìm nhị phân sẽ mất bao nhiêu phép so sánh?
- 2Bạn có mảng CHƯA sắp gồm 16 phần tử và cần tìm 3 lần. Sắp trước rồi tìm nhị phân, hay quét tuyến tính 3 lần?
- 3Vì sao `low + (high - low) / 2` được ưa dùng hơn `(low + high) / 2` trong C++ và Java?