កម្មវិធីបង្ហាញដំណើរការ Binary Search vs Linear Search

Linear search ពិនិត្យធាតុនីមួយៗម្តងមួយៗតាំងពីដើមរហូតដល់រកឃើញគោលដៅ។ Binary search ប្រើប្រាស់អត្ថប្រយោជន៍នៃ array ដែលបាន sorted រួច៖ វាមើលធាតុនៅចំកណ្តាល បើតូចពេក វានឹងលុបចោលផ្នែកខាងឆ្វេងទាំងមូល បើធំពេក វានឹងលុបផ្នែកខាងស្តាំចោល ហើយបន្តធ្វើបែបនេះលើផ្នែកដែលនៅសល់។ ទំព័រនេះដំណើរការវិធីទាំងពីរលើ sorted array តែមួយក្នុងពេលដំណាលគ្នា ដូច្នេះអ្នកអាចឃើញភាពខុសគ្នានៃចំនួនជំហានផ្ទាល់ភ្នែក។

Binary search បង្ហាញទ្រនិច lo, mid និង hi ហើយធ្វើឲ្យផ្នែកដែលបានកាត់ចោលទៅជាពណ៌ប្រផេះ។ សាកល្បងស្វែងរកធាតុនៅជិតចុងនៃ array ដែលមាន 100 ធាតុ៖ linear search ត្រូវការជិត 100 ជំហាន ចំណែក binary search ត្រូវការយ៉ាងច្រើន 7 ជំហានប៉ុណ្ណោះ។ សាកល្បងស្វែងរកតម្លៃដែលគ្មានក្នុង array ដើម្បីមើលថាតើវិធីនីមួយៗដឹងថាតម្លៃនោះមិនមានដោយរបៀបណា។

របៀបប្រើឧបករណ៍ Binary Search ទល់នឹង Linear Search

1. ជ្រើសរើស ទំហំ array ហើយបញ្ចូល តម្លៃគោលដៅ ឬចុច Random target ឬ Missing target។
2. ចុច Search។ ការស្វែងរកទាំងពីរនឹងចាប់ផ្តើមដំណាលគ្នា។
3. មើលប្រអប់ពណ៌ទឹកក្រូចដែលកំពុងពិនិត្យ ស្លាក lo, mid និង hi របស់ binary search ព្រមទាំងធាតុពណ៌ប្រផេះដែលត្រូវបានកាត់ចោល។
4. ប្រៀបធៀបចំនួនរាប់ជំហាន ហើយប្រើ Step និង Back ដើម្បីតាមដានការសម្រេចចិត្តរបស់ binary search។

ហេតុអ្វីប្រើ Binary Search ទល់នឹង Linear Search របស់ ToolOrca

• Linear search និង binary search ផ្ទាល់ភ្នែកលើទិន្នន័យតែមួយ
• ទ្រនិច lo, mid និង hi សម្រាប់ binary search
• ធាតុដែលកាត់ចោលបង្ហាញជាពណ៌ប្រផេះ
• រាប់ជំហានសម្រាប់ការស្វែងរកទាំងពីរ
• គោលដៅដែលមានក្នុងបញ្ជី និងមិនមានក្នុងបញ្ជី
• Pseudocode និងកូដជា C++, Java, Python និង JavaScript

របៀបដំណើរការរបស់ binary search

ចាប់ផ្តើមដោយ lo = 0 និង hi = n − 1។ ដរាបណា lo ≤ hi ត្រូវគណនា mid = (lo + hi) / 2 (បង្គត់ចុះ)។ ប្រសិនបើ a[mid] ស្មើនឹងតម្លៃគោលដៅ នោះគឺរួចរាល់។ ប្រសិនបើ a[mid] តូចជាង នោះតម្លៃគោលដៅអាចនៅតែខាងស្តាំប៉ុណ្ណោះ ដូច្នេះកំណត់ lo = mid + 1; បើមិនដូច្នោះទេ កំណត់ hi = mid − 1។ ប្រសិនបើ lo ធំជាង hi មានន័យថាតម្លៃគោលដៅមិនមានក្នុង array ទេ។

រាល់ជំហាននីមួយៗកាត់បន្ថយចន្លោះដែលនៅសល់ពាក់កណ្តាល ដូច្នេះ binary search ត្រូវការយ៉ាងច្រើនត្រឹម ⌊log₂ n⌋ + 1 ជំហាន៖ 7 ជំហានសម្រាប់ 100 ធាតុ, 20 ជំហានសម្រាប់មួយលានធាតុ និង 30 ជំហានសម្រាប់មួយពាន់លានធាតុ។ ក្នុងភាសាដែលមានទំហំ integer កំណត់ សូមសរសេរ mid = lo + (hi − lo) / 2 ដើម្បីការពារកុំឲ្យ overflow នៅពេល lo + hi មានតម្លៃធំខ្លាំង។

Linear search ទល់នឹង binary search

Linear search ដំណើរការលើ array ណាក៏បាន ទោះជា sorted ឬមិន sorted ហើយមានកម្រិត O(n)៖ ជាមធ្យមវាត្រូវពិនិត្យពាក់កណ្តាលនៃធាតុទាំងអស់។ Binary search មានកម្រិត O(log n) ប៉ុន្តែទាមទារឲ្យ array ត្រូវបាន sorted ជាមុន (និងអាច random access បាន ដូច្នេះវាមិនដំណើរការលើ linked list ទេ)។ ការ sort ជាមុនត្រូវចំណាយ O(n log n) ដូច្នេះ binary search មានប្រសិទ្ធភាពខ្ពស់នៅពេលអ្នកស្វែងរកលើទិន្នន័យដដែលច្រើនដង។

តើពេលណាគួរប្រើការស្វែងរកនីមួយៗ

ប្រើ linear search សម្រាប់ array តូចៗ, ទិន្នន័យមិនទាន់ sort ឬការស្វែងរកតែម្តងគត់។ ប្រើ binary search សម្រាប់ការស្វែងរកដដែលៗលើ sorted array និងទម្រង់កែប្រែរបស់វាដើម្បីស្វែងរកធាតុដំបូង ឬចុងក្រោយ, ចំណុចបញ្ចូល (bisect ក្នុង Python, lower_bound ក្នុង C++) ឬចម្លើយសម្រាប់បញ្ហាប្រភេទ “តម្លៃ x តូចបំផុតដែលផ្ទៀងផ្ទាត់លក្ខខណ្ឌ”។ Hash table ផ្តល់ការស្វែងរកល្បឿន O(1) ជាមធ្យម ប៉ុន្តែមិនរក្សាលំដាប់លំដោយឡើយ។

រាល់ visualizer លើគេហទំព័រនេះដំណើរការក្នុង browser របស់អ្នកជាមួយនឹងប៊ូតុងបញ្ជាដូចគ្នា៖ Play, Pause, ទៅមុខមួយជំហាន, ថយក្រោយមួយជំហាន និងរបារកំណត់ល្បឿន។ អ្នកក៏អាចអូសរបារទីតាំងដើម្បីផ្លោះទៅជំហានណាមួយ ឬចុចលើផ្ទាំងរូបភាពរួចប្រើ Space bar និងគ្រាប់ចុចព្រួញបានផងដែរ។