Viết một bài báo về Tìm kiếm nhị phân trong Javascript bằng tiếng Anh đơn giản cho trẻ em. Tiêu đề bài viết phải bắt mắt và thu hút người đọc. Giải thích phải ngắn gọn, rõ ràng và trực quan nhất có thể và ví dụ trực quan. Ngoài ra, bài viết nên bao gồm tiêu đề cho từng phần ở định dạng Markdown.
Tìm kiếm nhị phân là gì?
Bạn đã bao giờ muốn tìm một cái gì đó một cách nhanh chóng và dễ dàng? Tìm kiếm nhị phân là một cách nhanh chóng tìm thấy thứ gì đó trong danh sách các mục. Nó giống như một cuộc truy tìm kho báu, nhưng với những con số thay vì manh mối!
Tìm kiếm nhị phân hoạt động như thế nào?
Tìm kiếm nhị phân hoạt động bằng cách lấy danh sách các mục và chia đôi. Sau đó, nó nhìn vào số ở giữa danh sách. Nếu số đó là số chúng tôi đang tìm kiếm, thì chúng tôi đã tìm thấy nó! Nhưng nếu số không phải là số chúng tôi đang tìm kiếm, thì chúng tôi lại chia đôi danh sách và xem số ở giữa. Chúng tôi tiếp tục làm điều này cho đến khi chúng tôi tìm thấy con số mà chúng tôi đang tìm kiếm.
Tìm kiếm nhị phân trông như thế nào trong mã?
Giả sử chúng ta có một danh sách các số được gọi là numbers giống như sau:
1 2 | <span class="token punctuation">[</span> <span class="token number">1</span> <span class="token punctuation">,</span> <span class="token number">2</span> <span class="token punctuation">,</span> <span class="token number">4</span> <span class="token punctuation">,</span> <span class="token number">6</span> <span class="token punctuation">,</span> <span class="token number">8</span> <span class="token punctuation">,</span> <span class="token number">10</span> <span class="token punctuation">,</span> <span class="token number">12</span> <span class="token punctuation">,</span> <span class="token number">14</span> <span class="token punctuation">,</span> <span class="token number">16</span> <span class="token punctuation">,</span> <span class="token number">18</span> <span class="token punctuation">]</span> |
Đây là một ví dụ đơn giản về Tìm kiếm nhị phân được viết bằng Javascript:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | <span class="token keyword">function</span> <span class="token function">binarySearch</span> <span class="token punctuation">(</span> <span class="token parameter">numbers <span class="token punctuation">,</span> target</span> <span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token comment">// Set the start and end of our search</span> <span class="token keyword">let</span> start <span class="token operator">=</span> <span class="token number">0</span> <span class="token punctuation">;</span> <span class="token keyword">let</span> end <span class="token operator">=</span> numbers <span class="token punctuation">.</span> length <span class="token operator">-</span> <span class="token number">1</span> <span class="token punctuation">;</span> <span class="token comment">// Keep searching until we find the target</span> <span class="token keyword">while</span> <span class="token punctuation">(</span> start <span class="token operator"><=</span> end <span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token comment">// Find the middle of our search</span> <span class="token keyword">let</span> middle <span class="token operator">=</span> Math <span class="token punctuation">.</span> <span class="token function">floor</span> <span class="token punctuation">(</span> <span class="token punctuation">(</span> start <span class="token operator">+</span> end <span class="token punctuation">)</span> <span class="token operator">/</span> <span class="token number">2</span> <span class="token punctuation">)</span> <span class="token punctuation">;</span> <span class="token comment">// Check if the middle is the target</span> <span class="token keyword">if</span> <span class="token punctuation">(</span> numbers <span class="token punctuation">[</span> middle <span class="token punctuation">]</span> <span class="token operator">===</span> target <span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token keyword">return</span> middle <span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token comment">// If the middle is not the target, then </span> <span class="token comment">// check if it is greater or less than </span> <span class="token comment">// the target and adjust our search accordingly</span> <span class="token keyword">if</span> <span class="token punctuation">(</span> numbers <span class="token punctuation">[</span> middle <span class="token punctuation">]</span> <span class="token operator"><</span> target <span class="token punctuation">)</span> <span class="token punctuation">{</span> start <span class="token operator">=</span> middle <span class="token operator">+</span> <span class="token number">1</span> <span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token punctuation">{</span> end <span class="token operator">=</span> middle <span class="token operator">-</span> <span class="token number">1</span> <span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token punctuation">}</span> <span class="token comment">// If we don't find the target, then return -1</span> <span class="token keyword">return</span> <span class="token operator">-</span> <span class="token number">1</span> <span class="token punctuation">;</span> <span class="token punctuation">}</span> |
Hãy dùng thử!
Bây giờ bạn đã biết cách hoạt động của Tìm kiếm nhị phân, tại sao bạn không tự mình thử? Dưới đây là một ví dụ về cách bạn có thể sử dụng mã ở trên để tìm số 8 trong danh sách các số của chúng tôi:
1 2 3 4 5 6 7 | <span class="token keyword">let</span> numbers <span class="token operator">=</span> <span class="token punctuation">[</span> <span class="token number">1</span> <span class="token punctuation">,</span> <span class="token number">2</span> <span class="token punctuation">,</span> <span class="token number">4</span> <span class="token punctuation">,</span> <span class="token number">6</span> <span class="token punctuation">,</span> <span class="token number">8</span> <span class="token punctuation">,</span> <span class="token number">10</span> <span class="token punctuation">,</span> <span class="token number">12</span> <span class="token punctuation">,</span> <span class="token number">14</span> <span class="token punctuation">,</span> <span class="token number">16</span> <span class="token punctuation">,</span> <span class="token number">18</span> <span class="token punctuation">]</span> <span class="token punctuation">;</span> <span class="token keyword">let</span> target <span class="token operator">=</span> <span class="token number">8</span> <span class="token punctuation">;</span> <span class="token keyword">let</span> index <span class="token operator">=</span> <span class="token function">binarySearch</span> <span class="token punctuation">(</span> numbers <span class="token punctuation">,</span> target <span class="token punctuation">)</span> <span class="token punctuation">;</span> console <span class="token punctuation">.</span> <span class="token function">log</span> <span class="token punctuation">(</span> index <span class="token punctuation">)</span> <span class="token punctuation">;</span> <span class="token comment">// 4</span> |
Như bạn có thể thấy, chỉ số của số 8 là 4. Điều đó có nghĩa là nó là số thứ 5 trong danh sách của chúng tôi!
Ví dụ khác
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 | <span class="token comment">// An array of words in a dictionary, sorted alphabetically</span> <span class="token keyword">const</span> dictionaryWords <span class="token operator">=</span> <span class="token punctuation">[</span> <span class="token punctuation">{</span> index <span class="token operator">:</span> <span class="token number">1</span> <span class="token punctuation">,</span> word <span class="token operator">:</span> <span class="token string">"book"</span> <span class="token punctuation">}</span> <span class="token punctuation">,</span> <span class="token punctuation">{</span> index <span class="token operator">:</span> <span class="token number">3</span> <span class="token punctuation">,</span> word <span class="token operator">:</span> <span class="token string">"computer"</span> <span class="token punctuation">}</span> <span class="token punctuation">,</span> <span class="token punctuation">{</span> index <span class="token operator">:</span> <span class="token number">7</span> <span class="token punctuation">,</span> word <span class="token operator">:</span> <span class="token string">"dictionary"</span> <span class="token punctuation">}</span> <span class="token punctuation">,</span> <span class="token punctuation">{</span> index <span class="token operator">:</span> <span class="token number">9</span> <span class="token punctuation">,</span> word <span class="token operator">:</span> <span class="token string">"elephant"</span> <span class="token punctuation">}</span> <span class="token punctuation">,</span> <span class="token punctuation">{</span> index <span class="token operator">:</span> <span class="token number">80</span> <span class="token punctuation">,</span> word <span class="token operator">:</span> <span class="token string">"flower"</span> <span class="token punctuation">}</span> <span class="token punctuation">,</span> <span class="token punctuation">]</span> <span class="token punctuation">;</span> <span class="token keyword">function</span> <span class="token function">binarySearch</span> <span class="token punctuation">(</span> list <span class="token punctuation">,</span> item <span class="token punctuation">,</span> <span class="token function-variable function">filterCondition</span> <span class="token operator">=</span> <span class="token punctuation">(</span> <span class="token parameter">e</span> <span class="token punctuation">)</span> <span class="token operator">=></span> e <span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token comment">// Get the middle item of the list</span> <span class="token keyword">const</span> middle <span class="token operator">=</span> Math <span class="token punctuation">.</span> <span class="token function">floor</span> <span class="token punctuation">(</span> list <span class="token punctuation">.</span> length <span class="token operator">/</span> <span class="token number">2</span> <span class="token punctuation">)</span> <span class="token punctuation">;</span> <span class="token keyword">const</span> middleItem <span class="token operator">=</span> <span class="token function">filterCondition</span> <span class="token punctuation">(</span> list <span class="token punctuation">[</span> middle <span class="token punctuation">]</span> <span class="token punctuation">)</span> <span class="token punctuation">;</span> <span class="token comment">// If the item is the middle item, return it</span> <span class="token keyword">if</span> <span class="token punctuation">(</span> item <span class="token operator">===</span> middleItem <span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token keyword">return</span> list <span class="token punctuation">[</span> middle <span class="token punctuation">]</span> <span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token comment">// If the item is less than the middle item, search the first half of the list</span> <span class="token keyword">if</span> <span class="token punctuation">(</span> item <span class="token operator"><</span> middleItem <span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token keyword">return</span> <span class="token function">binarySearch</span> <span class="token punctuation">(</span> list <span class="token punctuation">.</span> <span class="token function">slice</span> <span class="token punctuation">(</span> <span class="token number">0</span> <span class="token punctuation">,</span> middle <span class="token punctuation">)</span> <span class="token punctuation">,</span> item <span class="token punctuation">,</span> filterCondition <span class="token punctuation">)</span> <span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token comment">// If the item is greater than the middle item, search the second half of the list</span> <span class="token keyword">if</span> <span class="token punctuation">(</span> item <span class="token operator">></span> middleItem <span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token keyword">return</span> <span class="token function">binarySearch</span> <span class="token punctuation">(</span> list <span class="token punctuation">.</span> <span class="token function">slice</span> <span class="token punctuation">(</span> middle <span class="token operator">+</span> <span class="token number">1</span> <span class="token punctuation">)</span> <span class="token punctuation">,</span> item <span class="token punctuation">,</span> filterCondition <span class="token punctuation">)</span> <span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token comment">// If the item is not found, return -1</span> <span class="token keyword">return</span> <span class="token operator">-</span> <span class="token number">1</span> <span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token keyword">const</span> word <span class="token operator">=</span> <span class="token function">binarySearch</span> <span class="token punctuation">(</span> dictionaryWords <span class="token punctuation">,</span> <span class="token number">3</span> <span class="token punctuation">,</span> <span class="token punctuation">(</span> <span class="token parameter">e</span> <span class="token punctuation">)</span> <span class="token operator">=></span> e <span class="token punctuation">.</span> index <span class="token punctuation">)</span> <span class="token punctuation">;</span> console <span class="token punctuation">.</span> <span class="token function">log</span> <span class="token punctuation">(</span> word <span class="token punctuation">)</span> <span class="token punctuation">;</span> <span class="token comment">// { index: 7, word: 'dictionary' }</span> |
Phần kết luận
Tìm kiếm nhị phân là một cách tuyệt vời để nhanh chóng tìm thấy thứ gì đó trong danh sách các mục. Nó nhanh chóng và hiệu quả và có thể được sử dụng để giải quyết nhiều loại vấn đề khác nhau. Bây giờ bạn đã biết cách hoạt động của Tìm kiếm nhị phân, tại sao không thử?
Và cuối cùng
Như mọi khi, tôi hy vọng bạn thích bài viết này và học được điều gì đó mới. Xin cảm ơn và hẹn gặp lại các bạn trong những bài viết tiếp theo!
Nếu các bạn thích bài viết này thì hãy cho mình 1 like và subscribe để ủng hộ mình nhé. Cảm ơn bạn.