ការស្វែងរក

មាតិកា

1. ការស្វែងរកជាការងារដែលធ្វើញឹកញាប់បំផុត
2. Linear Search
3. Binary Search
4. ហេតុអ្វីបានជាលឿនខ្លាំងម្ល៉េះ
5. អន្ទាក់ Off-by-One
6. Lower Bound និង Upper Bound
7. Binary Search លើ Rotated Array
8. Binary Search លើចម្លើយ
9. ការស្វែងរកក្នុងការអនុវត្តជាក់ស្តែង
10. រូបមន្ត៖ searching.ts សម្រាប់ algolab
11. សាកល្បងដោយខ្លួនឯង

1. ការស្វែងរកជាការងារដែលធ្វើញឹកញាប់បំផុត

កម្មវិធីភាគច្រើនចំណាយជីវិតទាំងមូលរបស់វាទៅលើការស្វែងរកអ្វីមួយ។ តើអ្នកប្រើណាមាន email នេះ? តើពាក្យនេះមាននៅក្នុងវចនានុក្រមឬទេ? តើ release ណាដែលបំបែក build ជាលើកដំបូង? តើទំហំ server តូចបំផុតអ្វីដែលអាចទ្រាំទ្របន្ទុកបាន?

របៀបដែលអ្នកស្វែងរកអាស្រ័យលើអ្វីដែលអ្នកដឹងអំពីទិន្នន័យ៖

• មិនដឹងអ្វីទាំងអស់៖ អ្នកត្រូវមើលធាតុម្តងមួយៗ។ នោះគឺជា linear search។
• ទិន្នន័យត្រូវបានតម្រៀបរួច៖ អ្នកអាចបោះបង់ទិន្នន័យពាក់កណ្តាលរាល់ពេលដែលមើលម្តង។ នោះគឺជា binary search។
• ទិន្នន័យស្ថិតក្នុង hash map៖ អ្នកលោតត្រង់ទៅរកវាតែម្តង (ជំពូកទី 3)។ នោះលឿនបំផុត ប៉ុន្តែដំណើរការបានតែសម្រាប់ការផ្គូផ្គងពិតប្រាកដប៉ុណ្ណោះ។

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

2. Linear Search

Linear search ពិនិត្យរាល់ធាតុចាប់ពីដើម រហូតដល់រកឃើញ target ឬអស់ធាតុ៖

function linearSearch<T>(items: T[], target: T): number {
  for (let i = 0; i < items.length; i++) {
    if (items[i] === target) return i;
  }
  return -1;
}

const ids = [42, 7, 19, 3, 88];

console.log(linearSearch(ids, 19)); // 2
console.log(linearSearch(ids, 50)); // -1

ការត្រឡប់ -1 សម្រាប់ "រកមិនឃើញ" គឺជាទំនៀមទម្លាប់ដែលខ្ចីមកពី Array.prototype.indexOf។ វាដំណើរការ ព្រោះគ្មាន index ពិតណាមួយជាលេខអវិជ្ជមានទេ។

ក្នុងករណីអាក្រក់បំផុត target នៅចុងក្រោយ ឬបាត់ ដូច្នេះយើងមើលធាតុទាំង n៖ O(n)។ ករណីល្អបំផុតគឺធាតុទីមួយ៖ O(1)។

JavaScript មាន linear search ស្រាប់រួចហើយ។ indexOf, includes, find និង findIndex ទាំងអស់ធ្វើ loop នេះឲ្យអ្នក។ ប្រើវានៅពេល array តូច ឬមិនទាន់តម្រៀប។ Linear search មិនមែន "អាក្រក់" ទេ៖ សម្រាប់ 50 ធាតុ វាលឿនជាងជម្រើសឆ្លាតវៃណាៗ ព្រោះគ្មានអ្វីត្រូវរៀបចំជាមុន។

3. Binary Search

គិតលេខមួយពី 1 ដល់ 100 ហើយឲ្យមិត្តភក្តិទាយ។ មិត្តភក្តិឆ្លាតនឹងនិយាយថា 50។ អ្នកនិយាយថា "ធំជាង"។ គាត់និយាយថា 75។ អ្នកនិយាយថា "តូចជាង"។ ការទាយនីមួយៗកាត់ជួរដែលនៅសល់ពាក់កណ្តាល។ ក្រោយការទាយច្រើនបំផុត 7 ដង គាត់នឹងទាយត្រូវ។ នោះគឺជា binary search។

លក្ខខណ្ឌតែមួយគត់៖ ទិន្នន័យត្រូវតែបានតម្រៀប។ បើគ្មានលំដាប់ទេ "ធំជាង" និង "តូចជាង" គ្មានន័យអ្វីឡើយ។

នេះគឺជា algorithm លើ sorted array។ រក្សា pointer ពីរ គឺ lo និង hi ព័ទ្ធជុំវិញផ្នែកដែលអាចនៅមាន target។ មើលធាតុកណ្តាល។ បើវាតូចពេក target ត្រូវតែនៅខាងស្តាំ។ បើវាធំពេក វាត្រូវតែនៅខាងឆ្វេង៖

function binarySearch(sorted: number[], target: number): number {
  let lo = 0;
  let hi = sorted.length - 1;

  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);

    if (sorted[mid] === target) return mid;
    if (sorted[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }

  return -1;
}

const scores = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91];

console.log(binarySearch(scores, 23)); // 5
console.log(binarySearch(scores, 7));  // -1
console.log(binarySearch(scores, 2));  // 0
console.log(binarySearch(scores, 91)); // 9

នេះគឺជា trace នៃការស្វែងរក 23។ "ជួរ" គឺពី lo ដល់ hi៖

មើលបីដងជំនួសឲ្យប្រាំមួយដង។ លើ 10 ធាតុ នោះគឺជាការឈ្នះតូចតាច។ ផ្នែកបន្ទាប់បង្ហាញថាហេតុអ្វីវាក្លាយជាអស្ចារ្យលើទិន្នន័យធំ។

4. ហេតុអ្វីបានជាលឿនខ្លាំងម្ល៉េះ

ជំហាននីមួយៗបែងចែកជួរជាពាក់កណ្តាល។ តើអ្នកអាចបែងចែក n ជាពាក់កណ្តាលបានប៉ុន្មានដងមុនឈានដល់ 1? ប្រហែល log₂ n ដង។ នេះគឺជា logarithm ពី ជំពូក Big-O ក្នុង Math for Programmers៖ ចំនួនដងនៃការបែងចែកជាពាក់កណ្តាល។

មួយពាន់លានធាតុ ហើយមើលតែ 30 ដងប៉ុណ្ណោះ។ ការបង្កើនទិន្នន័យទ្វេដង បន្ថែមតែ មួយ ជំហានប៉ុណ្ណោះ។

តោះវាស់វា។ រក្សាទុកកូដនេះជា bench-search.ts ក្នុង algolab (យើងនឹងបំប្លែង function ទាំងនេះទៅជា module ត្រឹមត្រូវក្នុងរូបមន្ត ដូច្នេះឥឡូវនេះគ្រាន់តែចម្លងចូល)៖

function linearSearch(items: number[], target: number): number {
  for (let i = 0; i < items.length; i++) {
    if (items[i] === target) return i;
  }
  return -1;
}

function binarySearch(sorted: number[], target: number): number {
  let lo = 0;
  let hi = sorted.length - 1;
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (sorted[mid] === target) return mid;
    if (sorted[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}

const big = Array.from({ length: 5_000_000 }, (_, i) => i * 2);
const worst = 9_999_998; // តម្លៃចុងក្រោយក្នុង array

let t = performance.now();
for (let i = 0; i < 100; i++) linearSearch(big, worst);
console.log("linear x100:", (performance.now() - t).toFixed(1), "ms");

t = performance.now();
for (let i = 0; i < 100; i++) binarySearch(big, worst);
console.log("binary x100:", (performance.now() - t).toFixed(3), "ms");

npx tsx bench-search.ts

នៅលើ laptop មួយ លទ្ធផលគឺ៖

linear x100: 188.0 ms
binary x100: 0.097 ms

លេខរបស់អ្នកនឹងខុសគ្នា ប៉ុន្តែគម្លាតនឹងធំសម្បើម៖ នៅទីនេះលឿនជាងប្រហែលពីរពាន់ដង។ ចំណុចប្រុងប្រយ័ត្នមួយ៖ binary search ត្រូវការទិន្នន័យដែលបានតម្រៀប។ បើទិន្នន័យរបស់អ្នកមកដល់ដោយមិនទាន់តម្រៀប អ្នកត្រូវតម្រៀបវាជាមុន (ជំពូកបន្ទាប់) ដែលចំណាយ O(n log n)។ វាបានផលតែនៅពេលអ្នកស្វែងរកច្រើនដង។ ស្វែងរកម្តងលើទិន្នន័យដែលមិនទាន់តម្រៀប? គ្រាន់តែប្រើ linear search។

5. អន្ទាក់ Off-by-One

Binary search ជាករណីបុរាណមួយ៖ គំនិតសាមញ្ញ ប៉ុន្តែព័ត៌មានលម្អិតងាយនឹងខុស។ Jon Bentley អ្នកដែលបានសរសេរសៀវភៅល្បីអំពីការសរសេរកម្មវិធី បានរាយការណ៍ថា នៅពេលគាត់ឲ្យអ្នកសរសេរកម្មវិធីអាជីពសរសេរវា មានតែមួយផ្នែកតូចប៉ុណ្ណោះដែលសរសេរត្រូវទាំងស្រុង។ កំហុសស្ទើរតែទាំងអស់ជា off-by-one error។ នេះគឺជាកន្លែងបួនដែលត្រូវពិនិត្យ។

1. លក្ខខណ្ឌ loop។ យើងសរសេរ while (lo <= hi) ព្រោះទាំង lo និង hi ត្រូវបាន រួមបញ្ចូល ក្នុងជួរ។ នៅពេល lo === hi នៅសល់ធាតុមួយ ហើយវានៅតែត្រូវពិនិត្យ។ បើអ្នកសរសេរ lo < hi អ្នកនឹងរំលងធាតុចុងក្រោយនោះ ហើយខកខាន target ដែលស្ថិតនៅទីនោះ។ សាកល្បងមើល៖ ស្វែងរក 2 ក្នុង [2]។

2. ការផ្លាស់ទី pointer។ បន្ទាប់ពីពិនិត្យ mid យើងដឹងថាវាមិនមែនជា target ដូច្នេះយើងផ្លាស់ទី ហួស វា៖ lo = mid + 1 និង hi = mid - 1។ បើអ្នកសរសេរ lo = mid វិញ នោះនៅពេល lo និង mid ដូចគ្នា គ្មានអ្វីប្រែប្រួលទេ ហើយ loop ដំណើរការជារៀងរហូត។

3. ការគណនាចំណុចកណ្តាល។ យើងសរសេរ lo + Math.floor((hi - lo) / 2) មិនមែន Math.floor((lo + hi) / 2) ទេ។ ក្នុង JavaScript លេខមានសុវត្ថិភាពរហូតដល់ប្រហែល 9 quadrillion ដូច្នេះ lo + hi នឹងមិន overflow សម្រាប់ array ពិតណាមួយឡើយ។ ប៉ុន្តែក្នុងភាសាដែលមាន integer 32-bit (Java, C) lo + hi អាច overflow សម្រាប់ array ដែលមានលើសមួយពាន់លានធាតុ។ កំហុសនេះឯងបានស្ថិតក្នុង standard library របស់ Java អស់រយៈពេលច្រើនឆ្នាំ។ ទម្រង់សុវត្ថិភាពមិនចំណាយអ្វីទេ ដូច្នេះប្រើវាជាទម្លាប់។

4. តម្លៃ hi ដំបូង។ ក្នុងកំណែនេះ hi = length - 1 ដែលជា index ត្រឹមត្រូវចុងក្រោយ ព្រោះជួរ រួមបញ្ចូលចុងទាំងពីរ។ កំហុសទូទៅមួយគឺច្រឡំរចនាប័ទ្ម៖ ចាប់ផ្តើមជាមួយ hi = length (មិនរួមបញ្ចូល) ប៉ុន្តែរក្សា loop lo <= hi និង hi = mid - 1។ បន្ទាប់មក sorted[hi] អាចជា undefined ហើយតក្កវិជ្ជាបែកបាក់។

ដំណោះស្រាយសម្រាប់ទាំងបួនគឺដូចគ្នា៖ ជ្រើសរចនាប័ទ្មមួយ ហើយនៅស្របគ្នា។ មានរចនាប័ទ្មពីរ៖

រចនាប័ទ្ម inclusive ខាងលើសមស្របសម្រាប់ "រកតម្លៃពិតប្រាកដនេះ"។ រចនាប័ទ្ម half-open ល្អជាងសម្រាប់ផ្នែកបន្ទាប់ ដែលចម្លើយអាចជា "ទីតាំងដែលវានឹងត្រូវដាក់" រួមទាំងទីតាំងហួសចុងមួយ។

6. Lower Bound និង Upper Bound

តើបើ array មានតម្លៃស្ទួនវិញ?

const data = [1, 2, 2, 2, 3, 5];

binarySearch(data, 2) ត្រឡប់ index មួយនៃ 2 ប៉ុន្តែមួយណា? វាអាស្រ័យលើកន្លែងដែល mid ធ្លាក់ចុះ។ ជារឿយៗអ្នកត្រូវការអ្វីដែលច្បាស់លាស់ជាងនេះ៖

• Lower bound៖ index នៃធាតុ ទីមួយ ដែល >= target។
• Upper bound៖ index នៃធាតុទីមួយដែល > target។

ទាំងពីរតែងតែមានតម្លៃ សូម្បីតែនៅពេល target បាត់ ព្រោះវាត្រឡប់ "កន្លែងដែលវានឹងត្រូវបញ្ចូល"។ នោះធ្វើឲ្យវាមានប្រយោជន៍ជាងការត្រឡប់ -1 ឆ្ងាយណាស់៖

function lowerBound(sorted: number[], target: number): number {
  let lo = 0;
  let hi = sorted.length; // half-open៖ hi អាចនៅហួសចុងមួយ

  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (sorted[mid] < target) lo = mid + 1;
    else hi = mid;
  }

  return lo;
}

function upperBound(sorted: number[], target: number): number {
  let lo = 0;
  let hi = sorted.length;

  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (sorted[mid] <= target) lo = mid + 1;
    else hi = mid;
  }

  return lo;
}

const data = [1, 2, 2, 2, 3, 5];

console.log(lowerBound(data, 2)); // 1  (first 2)
console.log(upperBound(data, 2)); // 4  (just after the last 2)
console.log(lowerBound(data, 4)); // 5  (4 would be inserted before 5)
console.log(lowerBound(data, 9)); // 6  (past the end)
console.log(lowerBound(data, 0)); // 0  (before everything)

function ទាំងពីរខុសគ្នាត្រឹមតួអក្សរតែមួយ៖ < ទល់នឹង <=។ អានវាជា "បន្តផ្លាស់ទីទៅស្តាំ ដរាបណាធាតុ តូចពេកមិនអាចជាចម្លើយ"។ សម្រាប់ lower bound "តូចពេក" មានន័យថា < target។ សម្រាប់ upper bound វាមានន័យថា <= target។

ល្បិចមានប្រយោជន៍បីដូចខាងក្រោមកើតឡើងភ្លាមៗ៖

// តើ target លេចឡើងប៉ុន្មានដង?
function countOf(sorted: number[], target: number): number {
  return upperBound(sorted, target) - lowerBound(sorted, target);
}

console.log(countOf(data, 2)); // 3
console.log(countOf(data, 4)); // 0

• មានឬទេ? lowerBound(a, x) < a.length && a[lowerBound(a, x)] === x។
• ទីតាំងបញ្ចូល៖ lowerBound ប្រាប់អ្នកថាត្រូវ splice ធាតុថ្មីចូលកន្លែងណា ដើម្បីរក្សា array ឲ្យបានតម្រៀប។
• Range query៖ "តើមានការបញ្ជាទិញប៉ុន្មានត្រូវបានធ្វើរវាង timestamp ពីរ?" គឺ lowerBound(end) - lowerBound(start) លើបញ្ជី timestamp ដែលបានតម្រៀប។ នេះគឺជារបៀបដែល range query របស់ database លើ index ដំណើរការ គ្រាន់តែប្រើ tree ជំនួស array។

7. Binary Search លើ Rotated Array

អ្នកសម្ភាសន៍ស្រលាញ់ប្រធានបទនេះ។ sorted array មួយត្រូវបាន បង្វិល នៅ pivot មួយចំណុច ដូច្នេះ [0, 1, 2, 4, 5, 6, 7] ក្លាយជា [4, 5, 6, 7, 0, 1, 2]។ រក target ក្នុង O(log n)។

array មិនត្រូវបានតម្រៀបទាំងស្រុងទៀតទេ ប៉ុន្តែការពិតសំខាន់មួយជួយ៖ បើអ្នកបំបែកវានៅ mid ណាមួយ យ៉ាងហោចណាស់ពាក់កណ្តាលមួយនៅតែតម្រៀប។ ពិនិត្យថាពាក់កណ្តាលណាតម្រៀប សួរថា "តើ target នៅក្នុងពាក់កណ្តាលដែលតម្រៀបនោះឬទេ?" ហើយរក្សា ឬបោះបង់ពាក់កណ្តាលនោះ៖

function searchRotated(nums: number[], target: number): number {
  let lo = 0;
  let hi = nums.length - 1;

  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (nums[mid] === target) return mid;

    if (nums[lo] <= nums[mid]) {
      // ពាក់កណ្តាលខាងឆ្វេង [lo..mid] ត្រូវបានតម្រៀប
      if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
      else lo = mid + 1;
    } else {
      // ពាក់កណ្តាលខាងស្តាំ [mid..hi] ត្រូវបានតម្រៀប
      if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
      else hi = mid - 1;
    }
  }

  return -1;
}

const rotated = [4, 5, 6, 7, 0, 1, 2];

console.log(searchRotated(rotated, 0)); // 4
console.log(searchRotated(rotated, 3)); // -1
console.log(searchRotated(rotated, 4)); // 0
console.log(searchRotated(rotated, 2)); // 6

កត់សម្គាល់ថា nums[lo] <= nums[mid] ប្រើ <= មិនមែន < ទេ។ នៅពេល lo === mid (ធាតុតែមួយ) "ពាក់កណ្តាលខាងឆ្វេង" គឺគ្រាន់តែជាធាតុតែមួយនោះ ហើយវាត្រូវបានរាប់ថាតម្រៀប។ ព័ត៌មានលម្អិតនេះគឺជាប្រភេទ off-by-one ដែលបរាជ័យក្នុង hidden test។ កំណែនេះសន្មតថាគ្មានតម្លៃស្ទួន៖ ជាមួយតម្លៃស្ទួន ករណីអាក្រក់បំផុតធ្លាក់ចុះទៅ O(n)។

8. Binary Search លើចម្លើយ

នេះគឺជាគំនិតដែលធ្វើឲ្យ binary search ក្លាយជាឧបករណ៍ទូទៅ។ អ្នកមិនត្រូវការ array ទេ។ អ្នកត្រូវការ សំណួរបាទ/ចាស ឬទេ ដែលប្តូរតែម្តង នៅពេលអ្នកដើរកាត់ចម្លើយដែលអាចមាន៖

answer:   1   2   3   4   5   6   7 ...
ok?:      no  no  no  yes yes yes yes ...

បើ "តើ x គ្រប់គ្រាន់ឬទេ?" គឺ ទេ សម្រាប់ x តូច និង បាទ/ចាស ចាប់ពីចំណុចណាមួយតទៅ (លក្ខខណ្ឌ monotonic) អ្នកអាច binary search រក "បាទ/ចាស" ដំបូងនោះ ដោយមិនចាំបាច់សាងសង់បញ្ជីឡើយ។ "array" គឺគ្រាន់តែជាជួរនៃចម្លើយបេក្ខភាព។

នេះគឺជា helper ដែលប្រើឡើងវិញបាន។ វារក x តូចបំផុតក្នុង [lo, hi] ដែល ok(x) ជាពិត ហើយសន្មតថា ok(hi) ជាពិត៖

function binarySearchAnswer(
  lo: number,
  hi: number,
  ok: (x: number) => boolean,
): number {
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (ok(mid)) hi = mid; // mid ដំណើរការ ប៉ុន្តែតម្លៃតូចជាងក៏អាចដំណើរការដែរ
    else lo = mid + 1;     // mid បរាជ័យ ដូច្នេះចម្លើយធំជាង
  }
  return lo;
}

ឧទាហរណ៍ទី 1៖ ល្បឿនញ៉ាំយឺតបំផុត។ ស្វាមួយមានគំនរចេកច្រើន និង hours ម៉ោងដើម្បីញ៉ាំឲ្យអស់។ រាល់ម៉ោង វាជ្រើសគំនរមួយ ហើយញ៉ាំរហូតដល់ speed ផ្លែពីវា (គំនរដែលតូចជាង speed នៅតែចំណាយម៉ោងទាំងមូល)។ តើល្បឿនតូចបំផុតអ្វីដែលញ៉ាំអស់ទាន់ពេល?

បើល្បឿន k ដំណើរការ ល្បឿនលឿនជាងណាក៏ដំណើរការដែរ ដូច្នេះលក្ខខណ្ឌប្តូរតែម្តង។ សម្រាប់ល្បឿនមួយ ការរាប់ម៉ោងគឺងាយ៖ គំនរនីមួយៗចំណាយ Math.ceil(pile / speed) ម៉ោង។

function minSpeed(piles: number[], hours: number): number {
  return binarySearchAnswer(1, Math.max(...piles), (speed) => {
    let total = 0;
    for (const p of piles) total += Math.ceil(p / speed);
    return total <= hours;
  });
}

console.log(minSpeed([3, 6, 7, 11], 8));      // 4
console.log(minSpeed([30, 11, 23, 4, 20], 5)); // 30
console.log(minSpeed([30, 11, 23, 4, 20], 6)); // 23

ហេតុអ្វីបានជា Math.max(...piles) ជាដែនកំណត់ខាងលើ? នៅល្បឿននោះ គំនរនីមួយៗចំណាយពេលមួយម៉ោងពិតប្រាកដ ដែលជាល្បឿនលឿនបំផុតដែលអាចមាន។ ការពិនិត្យនីមួយៗចំណាយ O(n) ហើយយើងធ្វើការពិនិត្យប្រហែល log₂(max) ដង ដូច្នេះទាំងមូលគឺ O(n log max)។ ការសាកល្បងគ្រប់ល្បឿនដោយ brute-force នឹងជា O(n × max)។

ឧទាហរណ៍ទី 2៖ square root ជា integer។ integer ធំបំផុត x ដែល x * x <= n។ ត្រឡប់សំណួរ៖ រក x ដំបូងដែល x * x > n ហើយបន្ទាប់មកថយក្រោយមួយ៖

function mySqrt(n: number): number {
  return binarySearchAnswer(0, n + 1, (x) => x * x > n) - 1;
}

console.log(mySqrt(0));  // 0
console.log(mySqrt(1));  // 1
console.log(mySqrt(8));  // 2
console.log(mySqrt(16)); // 4
console.log(mySqrt(17)); // 4

រូបមន្តដូចគ្នានេះដោះស្រាយ "ship packages within D days", "split an array into k parts with the smallest largest sum", "minimum time to repair cars" និងច្រើនទៀត។ លំនាំដែលត្រូវសម្គាល់គឺ៖ "រកតម្លៃអប្បបរមា (ឬអតិបរមា) ដែលលក្ខខណ្ឌមួយពិត" ហើយការពិនិត្យបេក្ខភាពតែមួយថោកជាងការរកចម្លើយដោយផ្ទាល់។

ដើម្បីស្វែងរកតម្លៃ អតិបរមា ដែលដំណើរការ ត្រូវត្រឡប់វា។ រកតម្លៃដំបូងដែលលក្ខខណ្ឌ បរាជ័យ ហើយដកមួយ ដូចដែលយើងបានធ្វើក្នុង mySqrt។

9. ការស្វែងរកក្នុងការអនុវត្តជាក់ស្តែង

កន្លែងដែលអ្នកជួបគំនិតទាំងនេះក្នុងការងារ៖

git bisect គឺជាការបង្ហាញដ៏ល្អបំផុត។ ជាមួយ 1,000 commit រវាង release ល្អ និង release អាក្រក់ វាត្រូវការ test ប្រហែល 10 ដង ដើម្បីចង្អុលមុខជនល្មើស។ ការពិនិត្យតាម linear អាចត្រូវការ 1,000។

ច្បាប់ដៃមួយចំនួន៖

• មិនទាន់តម្រៀប ហើយស្វែងរកម្តង៖ linear search។
• ស្វែងរកច្រើនដងលើទិន្នន័យដូចគ្នា៖ តម្រៀបម្តង (ឬរក្សាវាឲ្យបានតម្រៀប) ហើយបន្ទាប់មក binary search; ឬបង្កើត Map បើអ្នកត្រូវការតែការផ្គូផ្គងពិតប្រាកដ។
• ត្រូវការ "ជិតបំផុត", "ទីមួយដែលយ៉ាងហោចណាស់", ឬ "មានប៉ុន្មានក្នុងជួរ"៖ sorted array និងការស្វែងរក bound។ hash map មិនអាចធ្វើរឿងទាំងនេះបានទេ។
• ចម្លើយជា floating-point៖ binary search ក៏ដំណើរការដែរ ប៉ុន្តែ loop ចំនួនដងថេរ (ឧទាហរណ៍ 100) ជំនួសឲ្យការសាកល្បង lo < hi ព្រោះលេខទសភាគមិនដែលស្មើគ្នាពិតប្រាកដឡើយ។

10. រូបមន្ត៖ searching.ts សម្រាប់ algolab

បង្កើត src/searching.ts ហើយប្រមូល function ពីជំពូកនេះ៖

export function linearSearch<T>(items: T[], target: T): number {
  for (let i = 0; i < items.length; i++) {
    if (items[i] === target) return i;
  }
  return -1;
}

// ជួរ inclusive [lo, hi]។ ត្រឡប់ index ណាមួយដែលត្រូវគ្នា ឬ -1។
export function binarySearch(sorted: number[], target: number): number {
  let lo = 0;
  let hi = sorted.length - 1;
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (sorted[mid] === target) return mid;
    if (sorted[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}

// ជួរ half-open [lo, hi)។ index នៃធាតុទីមួយដែល >= target។
export function lowerBound(sorted: number[], target: number): number {
  let lo = 0;
  let hi = sorted.length;
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (sorted[mid] < target) lo = mid + 1;
    else hi = mid;
  }
  return lo;
}

// index នៃធាតុទីមួយដែល > target។
export function upperBound(sorted: number[], target: number): number {
  let lo = 0;
  let hi = sorted.length;
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (sorted[mid] <= target) lo = mid + 1;
    else hi = mid;
  }
  return lo;
}

export function countOf(sorted: number[], target: number): number {
  return upperBound(sorted, target) - lowerBound(sorted, target);
}

export function searchRotated(nums: number[], target: number): number {
  let lo = 0;
  let hi = nums.length - 1;
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (nums[mid] === target) return mid;
    if (nums[lo] <= nums[mid]) {
      if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
      else lo = mid + 1;
    } else {
      if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
      else hi = mid - 1;
    }
  }
  return -1;
}

// x តូចបំផុតក្នុង [lo, hi] ដែល ok(x) ជាពិត។ សន្មតថា ok(hi) ជាពិត
// ហើយ ok ប្តូរពី false ទៅ true តែម្តងប៉ុណ្ណោះ។
export function binarySearchAnswer(
  lo: number,
  hi: number,
  ok: (x: number) => boolean,
): number {
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (ok(mid)) hi = mid;
    else lo = mid + 1;
  }
  return lo;
}

export function minSpeed(piles: number[], hours: number): number {
  return binarySearchAnswer(1, Math.max(...piles), (speed) => {
    let total = 0;
    for (const p of piles) total += Math.ceil(p / speed);
    return total <= hours;
  });
}

export function mySqrt(n: number): number {
  return binarySearchAnswer(0, n + 1, (x) => x * x > n) - 1;
}

ឥឡូវនេះ test ក្នុង src/searching.test.ts។ Binary search សមនឹងទទួលបាន test ច្រើនជាងកូដភាគច្រើន ហើយ edge case សំខាន់៖ array ទទេ, ធាតុតែមួយ, ធាតុទីមួយ, ធាតុចុងក្រោយ, បាត់នៅចុងទាំងសងខាង៖

import { test } from "node:test";
import assert from "node:assert/strict";
import {
  linearSearch,
  binarySearch,
  lowerBound,
  upperBound,
  countOf,
  searchRotated,
  minSpeed,
  mySqrt,
} from "./searching.ts";

test("linearSearch finds the first match or returns -1", () => {
  assert.equal(linearSearch([42, 7, 19, 3, 88], 19), 2);
  assert.equal(linearSearch([42, 7, 19, 3, 88], 50), -1);
  assert.equal(linearSearch([], 1), -1);
});

test("binarySearch handles the edge cases", () => {
  const a = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91];
  assert.equal(binarySearch(a, 23), 5);
  assert.equal(binarySearch(a, 2), 0);   // first item
  assert.equal(binarySearch(a, 91), 9);  // last item
  assert.equal(binarySearch(a, 7), -1);  // missing, in the middle
  assert.equal(binarySearch(a, 1), -1);  // smaller than everything
  assert.equal(binarySearch(a, 100), -1); // bigger than everything
  assert.equal(binarySearch([], 5), -1);
  assert.equal(binarySearch([5], 5), 0);
});

test("binarySearch agrees with linearSearch on every value", () => {
  const a = Array.from({ length: 50 }, (_, i) => i * 3);
  for (let x = -2; x <= 150; x++) {
    assert.equal(binarySearch(a, x), linearSearch(a, x));
  }
});

test("lowerBound, upperBound and countOf with duplicates", () => {
  const d = [1, 2, 2, 2, 3, 5];
  assert.equal(lowerBound(d, 2), 1);
  assert.equal(upperBound(d, 2), 4);
  assert.equal(lowerBound(d, 4), 5);
  assert.equal(lowerBound(d, 9), 6);
  assert.equal(lowerBound(d, 0), 0);
  assert.equal(countOf(d, 2), 3);
  assert.equal(countOf(d, 4), 0);
});

test("searchRotated", () => {
  const r = [4, 5, 6, 7, 0, 1, 2];
  assert.equal(searchRotated(r, 0), 4);
  assert.equal(searchRotated(r, 3), -1);
  assert.equal(searchRotated(r, 4), 0);
  assert.equal(searchRotated(r, 2), 6);
  assert.equal(searchRotated([1], 1), 0);
});

test("binary search on the answer", () => {
  assert.equal(minSpeed([3, 6, 7, 11], 8), 4);
  assert.equal(minSpeed([30, 11, 23, 4, 20], 5), 30);
  assert.equal(minSpeed([30, 11, 23, 4, 20], 6), 23);
  assert.equal(mySqrt(0), 0);
  assert.equal(mySqrt(8), 2);
  assert.equal(mySqrt(16), 4);
  assert.equal(mySqrt(17), 4);
});

បន្ថែម export ទៅ src/index.ts៖

export * from "./searching.ts";

ដំណើរការ test៖

npx tsx --test

អ្នកគួរឃើញ test ទាំងអស់ជាប់។ test ដែលមានឈ្មោះថា "agrees with linearSearch on every value" គួរចងចាំ៖ នៅពេលអ្នកមានកំណែយឺតដែលត្រឹមត្រូវច្បាស់ និងកំណែលឿនដែលស្មុគស្មាញ ចូរប្រៀបធៀបពួកវាលើ input ច្រើន។ នេះគឺជារបៀបថោកបំផុតដើម្បីចាប់ off-by-one bug។

11. សាកល្បងដោយខ្លួនឯង

1. បំបែកវាដោយចេតនា។ ក្នុង binarySearch ប្តូរ lo <= hi ទៅ lo < hi។ តើ test មួយណាបរាជ័យមុនគេ ហើយ array តូចបំផុតអ្វីដែលបង្ហាញ bug? បន្ទាប់មកប្តូរ lo = mid + 1 ទៅ lo = mid ហើយស្វែងរកតម្លៃដែលបាត់។ តើមានអ្វីកើតឡើង ហើយហេតុអ្វី?
2. ទីតាំងបញ្ចូល។ សរសេរ insertSorted(sorted, value) ដែលត្រឡប់ array ថ្មីជាមួយ value ត្រូវបានបញ្ចូលនៅកន្លែងត្រឹមត្រូវ ដោយប្រើ lowerBound។ ហេតុអ្វីបានជាការបញ្ចូលចំកណ្តាល array នៅតែអាចចំណាយ O(n) ទោះបីការរកទីតាំងជា O(log n)? (ជំនួយ៖ ជំពូកទី 2។)
3. Version អាក្រក់ដំបូង (ការសម្ភាសន៍)។ version 1..n ត្រូវបាន release ហើយចាប់ពី version ណាមួយតទៅ គ្រប់ version ទាំងអស់អាក្រក់។ អ្នកមាន function isBad(v)។ រក version អាក្រក់ដំបូងដោយហៅតិចបំផុត។ តើ helper ណាមួយពីជំពូកនេះដោះស្រាយវាក្នុងមួយបន្ទាត់?
4. ស្វែងរកក្នុង sorted matrix (ការសម្ភាសន៍)។ matrix មួយមាន row ដែលតម្រៀបពីឆ្វេងទៅស្តាំ ហើយ row នីមួយៗចាប់ផ្តើមដោយលេខធំជាងលេខចុងក្រោយនៃ row ខាងលើ។ ស្វែងរក target ក្នុង O(log(rows × cols)) ដោយចាត់ទុកវាជា array វែងមួយ ហើយបំប្លែង index i ទៅជា [Math.floor(i / cols), i % cols]។
5. Ship in D days (ការសម្ភាសន៍)។ កញ្ចប់ដែលមានទម្ងន់ត្រូវបានដឹកជញ្ជូនតាមលំដាប់ ហើយកប៉ាល់ផ្ទុកបានច្រើនបំផុត capacity ក្នុងមួយថ្ងៃ។ រកសមត្ថភាពតូចបំផុតដែលដឹកអ្វីៗទាំងអស់ក្នុងរយៈពេល days ថ្ងៃ។ ប្រើ binarySearchAnswer។ តើតម្លៃល្អសម្រាប់ lo និង hi គឺអ្វី? (ជំនួយ៖ កញ្ចប់ធ្ងន់បំផុត និងផលបូកនៃកញ្ចប់ទាំងអស់។)
6. រកកំពូល (Peak finder)។ array មួយឡើងខ្ពស់យ៉ាងតឹងរ៉ឹង ហើយបន្ទាប់មកចុះក្រោមយ៉ាងតឹងរ៉ឹង ដូចជា [1, 3, 8, 12, 9, 4, 2]។ រក index នៃកំពូលក្នុង O(log n)។ ប្រៀបធៀប a[mid] ជាមួយ a[mid + 1] ដើម្បីសម្រេចថារក្សាផ្នែកណាមួយ។

ការស្វែងរកនាំអ្នកពី "មើលអ្វីៗទាំងអស់" ទៅ "មើលស្ទើរតែគ្មានអ្វីសោះ" ភ្លាមៗដែលទិន្នន័យរបស់អ្នកមានលំដាប់ខ្លះ។ ប៉ុន្តែយើងបានសន្មតថាទិន្នន័យត្រូវបានតម្រៀបរួចហើយ ហើយក្នុងជីវិតពិតវាកម្រណាស់។ ក្នុងជំពូកបន្ទាប់ ការតម្រៀប យើងនឹងសាងសង់ algorithm តម្រៀបបុរាណ រកមើលថាហេតុអ្វីបានជា [10, 9, 1].sort() ផ្តល់ចម្លើយគួរឲ្យភ្ញាក់ផ្អើល និងវាស់ថាមួយណាដែលអ្នកអាចទ្រាំទ្របានពិតប្រាកដ។