บทความ เข้าสู่เนื้อหา
Data Structures and Algorithms Fundamentals

Binary Search คืออะไร?

3

Problem Statement

ในบทนี้เราจะมาทำความรู้จักกับหนึ่งใน algorithm ที่ “simple but yet powerful” ที่สุดนั่นก็คือ ‘Binary search’ นั่นเอง! แต่ก่อนที่จะเข้าเนื้อหากัน เรามาเริ่มจากปัญหาง่าย ๆ กันก่อนดีกว่า

“ณ ห้องสมุดแห่งหนึ่งมีชั้นวางหนังสือที่เรียงตามตัวอักษรของชื่อหนังสือ หากคุณต้องการหาหนังสือเล่มหนึ่งจากชื่อหนังสือ คุณจะใช้วิธีใดในการค้นหาเพื่อให้เจอหนังสือเล่มนั้นอย่างรวดเร็วและมีประสิทธิภาพที่สุด?”

ถ้าเราคิดไว ๆ วิธีการหนึ่งที่สามารถทำได้ก็คือการ “ไล่หาตั้งแต่หนังสือเล่มแรกจนถึงเล่มสุดท้าย” (หรือที่เราเรียกกันว่า ‘Linear search’)

สมมุติว่าในห้องสมุดแห่งนี้มีหนังสือทั้งหมด \(2^{15}\) หรือ 32,768 เล่ม และการไล่เช็คไปทีละเล่มใช้เวลา 1 วินาที ในกณีที่แย่ที่สุดเราจะใช้เวลาถึง 32,768 วินาทีหรือ 9 ชั่วโมงเลยทีเดียว

เรามักเรียกวิธีการแก้ปัญหาที่ obvious และตรงไปตรงมาที่สุดนี้ว่า ‘Naive solution’; สามารถอ่านเรื่องนี้เพิ่มเติมได้ในบทความ “การเปลี่ยนมุมมอง กับอัลกอริทึม Sieve of Eratosthenes” ⤵ อ่านเพิ่มเติม

แน่นอนว่า 9 ชั่วโมงกับการหาหนังสือเล่มนึงก็คงจะใช้เวลานานไปหน่อย แต่โชคยังดีที่ว่าหนังสือชั้นนี้ “เรียงตามตัวอักษรของชื่อหนังสือ” คำถามก็คือว่า เราสามารถใช้ observation ข้อนี้ในการพัฒนา algorithm ที่เร็วกว่าวิธีการแรกได้ไหม?

ถ้าหากว่าแทนที่เราจะไล่หาหนังสือตั้งแต่เล่มแรก เราเริ่มจากเริ่มหาตรงกลาง ๆ ของชั้นหนังสือแทนหละ? จากนั้นก็ค่อย ๆ ขยับไปหาในทิศทางที่เข้าไกล้กับหนังสือที่เรากำลังจะหาไปเรื่อย ๆ (เพราะชั้นหนังสือเรียงตามอักษรอยู่แล้ว) จนกระทั่งเจอ

เหมือนกับเวลาที่เราอยากจะเปิดหนังสือหน้า 375 เราอาจจะเริ่มจากสุ่มเปิดหนังสือสักหน้าก่อน อาจจะเป็นกลาง ๆ เล่ม จากนั้นดูว่าหน้าที่เปิดคือหน้าที่เท่าไหร่ ถ้าสมมุติว่าเปิดมาเจอหน้า 260 นั่นก็หมายความว่าหน้า 375 จะต้องอยู่ในครึ่งหลังของหนังสือแน่นอน ดังนั้นเราก็จะสุ่มเปิดหนังสือครึ่งหลังต่อไป ทำไปเรื่อย ๆ จนเจอหน้า 375

จะเห็นว่าวิธีการนี้มันคือการ scope down สิ่งที่เราต้องการหาไปเรื่อย ๆ ทีละครึ่ง แทนที่เราจะต้องนั่งไล่หาไปทีละตัวเหมือนแบบแรก ซึ่งเป็นอะไรที่เสียเวลากว่ามาก

โดยสรุปแล้วเราสามารถเขียนวิธีแก้ปัญหาออกมาคร่าว ๆ ได้แบบนี้

  1. เริ่มจากเช็คตรงกลางของชั้นหนังสือก่อน
  2. ถ้าชื่อหนังสือที่เราเจอมาก่อนชื่อหนังสือที่เรากำลังหาอยู่; ไปหาครึ่งหลัง (โดยเช็คจากตรงกลางของครึ่งหลัง เหมือนที่เราทำในข้อ 1)
  3. ในทางกลับกัน; ไปหาครึ่งหน้า
  4. ทำไปเรื่อย ๆ จนกว่าจะเจอหนังสือที่เราต้องการหา; ถ้าหากว่าเราหาจนช่วงของเราไม่เหลือหนังสือเล่มไหนอีกแล้ว ก็แสดงว่าไม่มีหนังสือเล่มนั้นอยู่ในชั้น

ซึ่งวิธีแก้ปัญหาที่เรากำลังทำอยู่นี้ก็คือ algorithm ที่เรียกว่า ‘Binary search’ นั่นเองครับ

Binary search คือ search algorithm หนึ่งที่ใช้หา position หรือ index ของ target value ใน ‘Sorted array’; ถ้าหากว่าไม่มีค่า target ใน arr นั้นก็จะ return ค่า null ออกมา

binarySearch(arr, target)\text{binarySearch(arr, target)}

โดยสำหรับการ implement binarySearch โดยปกติแล้วจะนิยมสร้างตัวแปร pointer ขึ้นมา 3 ตัว โดยสองตัวแรกได้แก่ left กับ right ไว้สำหรับกำหนดช่วงที่เรากำลังค้นหา target อยู่ (หรือในบางที่อาจจะใช้คำว่า low หรือ high)

ในตอนแรกเราจะกำหนดให้ left = 0 และ right = arr.length - 1

ส่วนค่าที่สามก็คือค่า mid ซึ่งเป็นค่าตรงกลางระหว่าง left และ right โดยสามารถคำนวนได้จาก

mid=⌊left+right2⌋mid = \left \lfloor{\frac{left + right}{2}}\right \rfloor
อ่านว่า mid = (left + right) / 2 ปัดลง

หลังจากนั้นที่เราต้องทำก็คือไล่เช็คค่า mid และอัพเดตค่า left, right ไปเรื่อย ๆ (scope down ไปเรื่อย ๆ) จนกระทั้งไม่เหลือค่าที่เราต้องหาอีกแล้วนั่นเอง (หยุดทำงานเมื่อ left > right)

โดยสรุปแล้วเราสามารถเขียน algorithm หรือ pseudo code ออกมาได้ดังนี้

  1. เซ็ตค่า left = 0 และ right = arr.length - 1
  2. เช็คถ้าหากว่า left > right ให้จบการทำงาน; ถ้าไม่ก็ไปทำข้อ (3)
  3. คำนวนค่า mid จากนั้นเช็คค่า arr[mid]
    1. ถ้าหากว่า arr[mid] < target; เซ็ต left = mid + 1 (หาครึ่งหลัง) และกลับไปที่ (2)
    2. ถ้าหากว่า arr[mid] > target; เซ็ต right = mid - 1 (หาครึ่งหน้า) และกลับไปที่ (2)
    3. ถ้าหากว่า arr[mid] = target; return ค่า mid ออกมาเป็นคำตอบ

สามารถลองกดเล่นเพื่อความเข้าใจเพิ่มเติมด้านล่างได้เลยครับ ⤵

Binary Search

Target =
Operation cost = 0
left = 0
right = 31
mid = null
1
0
4
1
9
2
11
3
16
4
19
5
23
6
27
7
28
8
33
9
38
10
40
11
45
12
49
13
54
14
55
15
60
16
65
17
70
18
74
19
76
20
78
21
79
22
84
23
86
24
89
25
94
26
95
27
98
28
103
29
104
30
105
31
1 / 16
ในตอนเริ่มต้น กำหนดให้ left = 0, right = 31 และค่า target = 60

สำหรับ Time complexity สังเกตว่าการเช็คค่า mid ในแต่ละรอบนั้น เราจะสามารถ scope สิ่งที่เราต้องค้นหาลงไปได้ทีครึ่งหนึ่ง และเราจะ scope ไปเรื่อย ๆ จนกระทั่งเหลือตัวสุดท้าย ซึ่งเราสามารถเขียนเป็นลำดับได้ดังนี้

N,N2,N4,N8,...,1N, \frac{N}{2}, \frac{N}{4}, \frac{N}{8}, \text{...}, 1

คำถามก็คือเราต้องหาร 2 ทั้งหมดกี่ครั้งจนกระทั่งเหลือ 1? จากลำดับข้างต้น เราสามารถให้จำนวนครั้งแทนด้วยตัวแปร \(k\) และเขียนสมการออกมาได้ว่า

N2k=1\frac{N}{2^k} = 1

ซึ่งเราสามารถแก้สมการหาค่า \(k\) ออกมาได้ว่า

N=2k log2N=log22k k=log2NN = 2^k \\ \text{ } \\ log_2{N} = log_2{2^k} \\ \text{ } \\ k = log_2{N}

ในกรณีที่แย่ที่สุดเราต้อง loop ทั้งหมด \(\left \lfloor{log_2{N} + 1}\right \rfloor\) ครั้ง (ที่ +1 เพราะถึงแม้ว่าเหลือตัวเดียวเราก็ต้อง loop เพื่อ compare ค่า mid) จากตรงนี้เราสามารถสรุปออกมาได้ว่า Binary search มี Time complexity เป็น \(O(log_2N)\) หรือ \(O(logN)\) นั่นเอง

ส่วน Space complexity ของ Binary search คือ \(O(1)\) เพราะการเก็บค่าลง memory ไม่ได้ขึ้นอยู่กับ input size (เก็บแค่ left, right และ mid)

Log หรือ logarithm ถ้าอธิบายแบบง่าย ๆ มันคือส่วนกลับของ exponential เรารู้ว่า \(2^5 = 32\); logarithm มันคือการถามว่า “เราต้องคูณ 2 ทั้งหมดกี่ครั้งเพื่อให้ได้ 32?” เราสามารถเขียนออกมาได้ว่า \(log_232 = 5\)

จะเห็นว่าถ้าเราเอา Time complexity ไปเทียบกับ Linear search แล้ว ถ้าหากว่ากำหนดให้ arr.length มีค่าเท่ากับ \(2^{30}\) ในกรณีที่แย่ที่สุด Linear search ต้องรันทั้งหมด 1,073,741,824 ครั้ง ในขณะที่ Binary search จะรันเพียงแค่ 31 ครั้งเท่านั่น

นี่หละคือความทรงพลังของ Binary search

Implementation

เชื่อว่าทุกคนน่าจะเข้าใจกันแล้วว่า Binary search ทำงานยังไง คราวนี้ก็ถึงเวลาที่เราจะมาลอง implement กัน

1
function binarySearch(arr, target) {
2
  let left = 0;
3
  let right = arr.length - 1;
4


5
  while (left <= right) {
6
      let mid = Math.floor(left + (right - left) / 2);
7


8
      if (arr[mid] === target) return mid;
9
      else if (arr[mid] < target) left = mid + 1;
10
      else right = mid - 1;
11
  }
12


13
  return null;
14
}

ดูการ implement ‘Binary search’ โดยใช้ recursion ได้ในคอร์ส Data Structures and Algorithms Fundamentals บทที่ 4, ‘Recursion’ เข้าสู่เนื้อหา

โค้ดข้างต้นนี้เป็น JS implementation ของ Binary search; ถ้าเราลองดูเราก็จะพบว่าหลาย ๆ อย่างมันก็เหมือนกับ psudo code ที่เราเขียนกันไปนั่นหละ เว้นเสียแต่ว่า … ทำไมเราถึงคำนวนค่า mid แปลก ๆ แบบนี้หละ?

1
let mid = Math.floor(left + (right - left) / 2);
2
// Why not? Math.floor((left + right) / 2);

“Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky” — Donald Knuth

ถึงแม้ Binary search โดยคอนเซ็ปแล้วจะเป็นอะไรที่เรียบง่ายและตรงไปตรงมา แต่การ implement กลับไม่ได้ง่ายตามไปด้วยนัก

การที่เราต้องเช็ค condition ต่าง ๆ รวมไปถึง pointer อย่าง left, right, mid ให้ถูกต้องเพื่อป้องกันไม่ให้เกิด infinite loop หรือการที่เราต้องคำนวน mid ให้ถูกต้องเพื่อป้องกันการเกิด integer overflow เมื่อ arr size ของเราใหญ่มาก ๆ (ซึ่งเป็นบัคที่ทุกคนมองข้ามมาเกือบ 20 ปี)

สิ่งเหล่านี้คือความยากและความจุกจิกของการ implement ทั้งสิ้น ซึ่งความยุ่งยากเหล่านี้ยังรวมไปถึงการนำ Binary search ไปดัดแปลงเพื่อเอาไปใช้แก้ปัญหาอื่น ๆ อีกด้วย

“While the first binary search was published in 1946, the first binary search that works correctly for all values of n did not appear until 1962.” — Jon Bentley, Programming Pearls.

จาก survey เมื่อปี 1988 พบว่า จาก textbook 20 เล่ม มีเพียงแค่ 5 เล่มเท่านั้นที่ implement binary search ได้ถูกต้องโดยไม่มี error ใด ๆ (กดอ่านเพิ่มเติมเพื่อดู error ที่เกิดขึ้นได้ใน section V. The Errors และผลจากการ survey ใน section IX. Postscript) อ่านเพิ่มเติม

การปรับใช้เพื่อแก้ปัญหาอื่น ๆ

เพื่อให้เห็นภาพการปรับใช้ Binary search มากขึ้น เราเลยอยากจะชวนทุกคนมาลองทำโจทย์ง่าย ๆ กันสักเล็กน้อย โจทย์บางส่วนเป็นโจทย์ที่ทุกคนสามารถเข้าไปลองทำกันได้ที่เว็บ LeetCode นะครับ ไว้ในแต่ละข้อจะแปะ link ที่เกี่ยวข้องเอาไว้เผื่อว่าใครอยากจะลองไปทำก่อนอ่านเฉลย

Sqrt(x)

ลองทำโจทย์ก่อนได้ที่ leetcode.com/problems/sqrtx

“กำหนดให้ตัวแปร \(x\) ให้เขียนโปรแกรมเพื่อหาค่า square root ของ \(x\) โดยปัดค่าลงให้เป็นจำนวนเต็มบวกที่ไกล้ที่สุด”

ยกตัวอย่างเช่นถ้า \(x = 4\) คำตอบก็คือ 2; ถ้า \(x = 8\) คำตอบก็คือ 2 เหมือนกัน (เพราะ square root ของ 8 คือประมาณ 2.82842… ซึ่งปัดลงจะเหลือ 2)

คำถามก็คือถ้าหากว่าเราจะแก้ปัญหาข้อนี้โดยที่ไม่ใช้ math libary หรือ function อย่างเช่น Math.sqrt เราจะทำยังไง?

“Square root of a number is a value, which on multiplication by itself, gives the original number.”

เราอาจจะเริ่มจาก naive solution ก่อนก็ได้โดยเราอาจจะ ลองไล่ loop i ตั้งแต่ 1 ถึง x; จากนั้นก็ลองเช็คว่า i * i ≤ x หรือไม่ ถ้า condition เป็น true ก็เก็บค่าเอาไว้ ส่วนถ้า false ก็แค่ break และ return คำตอบออกมา

1
function mySqrt(x) {
2
  let result = 0;
3


4
  for (let i = 1; i <= x; ++i) {
5
    if (i * i <= x) result = i;
6
    else break;
7
  }
8


9
  return result;
10
}

Time Complexity ของวิธีการนี้คือ \(O(sqrt(x))\)

หลายคนพอเริ่มถึงตรงนี้น่าจะพอเดาได้แล้วว่า “ในเมื่อเราสามารถบอกทิศทางได้ว่า i * i มันน้อยกว่าหรือมากกว่า \(x\)” แทนที่เราจะไล่หาไปทีละตัว ทำไมเราไม่ลองเลือกเลขกลาง ๆ มาสักตัว จากนั้นก็ค่อย ๆ scope down คำตอบไปเรื่อย ๆ หละ?

  1. คำนวนค่า mid ระหว่าง 1 ถึง \(x\) (left = 1, right = x)
  2. เช็คว่า mid * mid ≤ x หรือป่าว
    1. ถ้าใช่ก็ไปหาต่อครึ่งหลังและเก็บคำตอบเอาไว้ด้วย: left = mid + 1
    2. ถ้าไม่ก็หาต่อครึ่งหน้า: right = mid - 1
  3. ทำไปเรื่อย ๆ จน break (left > right) และ return คำตอบที่เก็บไว้ออกมา

1
function mySqrt(x) {
2
  let left = 1;
3
  let right = x;
4
  let result = 0;
5


6
  while (left <= right) {
7
    let mid = Math.floor(left + (right - left) / 2);
8


9
    if (mid * mid <= x) {
10
      result = mid;
11
      left = mid + 1;
12
    } else {
13
      right = mid - 1;
14
    }
15
  }
16


17
  return result;
18
}

Time Complexity: \(O(log_2{x})\) หรือ \(O(logx)\)

Find Peak Element

ลองทำโจทย์ก่อนได้ที่ leetcode.com/problems/find-peak-element

Peak element คือค่าที่มีค่ามากกว่าค่าข้าง ๆ ที่อยู่ติดกัน; arr[i] เป็น peak element ก็ต่อเมื่อ arr[i] > arr[i+1] และ arr[i] > arr[i-1]

กำหนดให้ nums เป็น array ของจำนวนเต็ม; ให้เขียนโปรแกรมเพื่อหาค่า peak element ใน nums (และ return ค่าออกมาเป็น index ของ peak นั้น) โดยที่สามารถ return ค่า index ของ peak ไหนออกมาก็ได้ (nums สามารถมีได้หลาย peak)

(รายละเอียดเพิ่มเติม: nums[i] != nums[i+1] และ nums[-1] = nums[n] = -∞)

ยกตัวอย่างเช่น nums = [1,2,3,1] คำตอบก็คือ ‘2’ เพราะ arr[2] หรือ ‘3’ คือ peak element

หรือถ้าให้ nums = [1,2,1,3,5,6,4] ข้อนี้จะตอบ ‘1’ หรือ ‘5’ ก็ได้เพราะ arr[1] และ arr[5] ล้วนเป็น peak element ด้วยกันทั้งนั้น

Find Peak Element - Input Structure

ถ้าหากว่าเราลองวาด structure ของ nums คร่าว ๆ ก็จะได้ประมาณนี้เลย หรือเราอาจจะลองจินตนาการถึงภาพของภูเขาก็ได้ โดยภาพด้านบนนี้จะเห็นว่ามี peak element อยู่ 3 จุดด้วยกัน

แน่นอนว่าข้อนี้เราจะ loop แล้วไล่หาค่า peak ตรง ๆ มันก็ได้ แต่ถ้าเราลองสังเกต structure ดี ๆ เราก็จะพบว่า “ข้อมูลนี้มันมีทิศทางที่ทำให้เราสามารถตัดสินใจและเข้าไกล้ผลลัพธ์ที่เราต้องการอยู่”

ถ้าเราลองจิ้มไปที่ (1) คำถามคือเรารู้ไหมว่า peak อยู่ทางไหน? คำตอบก็คือรู้ใช่ไหมครับก็คือทางขวานั่นเอง ทำไมถึงรู้? ก็เพราะว่าจุด (1) กำลังอยู่ในช่วงขาขึ้นนั้นเอง

จุด (2) ก็เช่นกันที่เรารู้ว่าค่า peak จะอยู่ฝั่งซ้าย อารมณ์เดียวกับการเดินเขานั้นหละที่เราจะเดินไปในทิศทางที่สูงขึ้นเพื่อให้ไปถึงยอดเขา

จากข้อสรุปตรงนี้เอง เราสามารถเขียน algorithm ออกมาได้ว่า

  1. คำนวนค่า mid ระหว่าง 1 (left) ถึง nums.length - 1 (right)
  2. เช็ค condition เพื่อหาค่า peak element
    1. ถ้า nums[mid + 1] > nums[mid]: หาในช่วงทางขวา (เคสเดียวกับจุดที่ (1) ในรูป)
    2. ถ้า nums[mid - 1] > nums[mid]: หาในช่วงทางซ้าย (เคสเดียวกับจุดที่ (2) ในรูป)
    3. ถ้าหากว่า nums[mid] มีค่ามากกว่า nums[mid - 1] และ nums[mid + 1]: แสดงว่าเจอ peak element แล้ว ก็ return ค่านั้นออกมาเป็นคำตอบ

1
function findPeakElement(nums) {
2
  let left = 0;
3
  let right = nums.length - 1;
4


5
  while (left <= right) {
6
    let mid = Math.floor(left + (right - left) / 2);
7


8
    if ((nums[mid + 1] || -Infinity) > nums[mid]) {
9
      left = mid + 1;
10
    } else if ((nums[mid - 1] || -Infinity) > nums[mid]) {
11
      right = mid - 1;
12
    } else {
13
      return mid;
14
    }
15
  }
16


17
  return null;
18
}

Time Complexity: \(O(log(\text{nums.length}))\)

บทสรุป

จากที่เราได้ลองทำโจทย์ไปหลายคนอาจจะตกใจว่า “Binary search มาเอามาใช้แก้ปัญหากับ array ที่มันไม่ได้ sort ได้ด้วยหรอ?” (เช่นในข้อ Find Peak Element)

จริง ๆ ก็ต้องบอกว่าไม่ใช่ว่าข้อมูลไม่ได้ sort ครับ เพียงแต่ว่าหลายครั้งเวลาเราพูดถึงคำว่า sort หรือ ‘การจัดเรียง’ เรามักจะติดกับภาพของการ ‘เรียงจากมากไปน้อย’ หรือ ‘จากน้อยไปมาก’ ก็เท่านั้นเอง (อันนี้ based on ที่เราเคยได้ไปคุยมากับหลาย ๆ คนที่เรียนเรื่องนี้)

Sort (n) “The arrangement of data in a prescribed sequence.”

การ sort มันเป็นอะไรที่มากกว่าการเรียงจากน้อยไปมากหรือมากไปน้อย มันคือการจัดเรียงข้อมูลตามรูปแบบที่เรากำหนดมันไว้ล่วงหน้าอยู่แล้ว

สำหรับเราแล้ว core idea ของ Binary search มันคือ “การเข้าใจทิศทางของข้อมูลที่มันทำให้เราสามารถตัดสินใจเพื่อเข้าไกล้คำตอบได้ไปเรื่อย ๆ” นั่นเป็นเหตุผลว่าทำไมข้อมูลต้อง sort มาก่อน

หรือถ้าเราลองพูดในอีกมุมนึงมันก็คือ

“การที่เรารู้และเข้าใจรูปแบบข้อมูลที่ชัดเจน มันทำให้เราสามารถคิด algorithm ที่ดีกว่าได้ ที่ take advantage จากรูปแบบข้อมูลเหล่านั้น แทนที่จะใช้วิธีการแก้ปัญหาแบบ general ได้”

Binary search มันคือการ take advantage หรือ leverage ความเข้าใจในข้อมูลแบบนึงนั่นหละ

วิธีการแก้ปัญหาหรือ Solution ที่ดีเกิดขึ้นมาได้อย่างไร?
วิธีการแก้ปัญหาหรือ ‘Solution’ เกิดมาจากอะไร? Pattern นำไปสู่วิธีแก้ปัญหาที่ดีขึ้นได้อย่างไร? และเราสามารถ maximize pattern อย่างไรได้บ้าง?
April 24, 2024 | 10 mins read
สามารถอ่านต่อเรื่องของการ ‘Leverage Pattern’ เพิ่มเติมได้ที่บทความข้างต้นเลยครับ

Exercises

  1. ถ้าเราจะอธิบาย Binary search ให้เด็ก 5 ขวบฟัง เราจะอธิบายยังไง?
  2. เราสามารถเอา Binary search ไป apply กับอะไรอย่างอื่นรอบตัวได้บ้าง?
  3. ถ้าหาก target ของเรามีค่าที่ซ้ำกันหลายค่าใน sorted arr แล้วเราอยากจะให้ Binary search return ค่า index ตัวแรกของ target (leftmost element) เราจะแก้ binary search algorithm ของเราอย่างไร?
  4. ถ้าหากว่าเราอยากจะ search ข้อมูลบน infinite sorted list (ไม่มี upper bound) เราสามารถ modify binary search อย่างไรได้บ้าง? (Hint: Exponential search)

Challenge Problem

จงหาตัวเลขที่น้อยที่สุดใน sorted array (arr) แต่ว่า array ดังกล่าวได้ถูกหมุนค่าโดยใครบางคนเช่น [1, 2, 3, 4, 5] ถ้าหากว่าโดนหมุน array นี้ไปทางขวา 2 ครั้ง ก็จะได้ array ใหม่คือ [3, 4, 5, 1, 2]

ให้เราหาค่าที่น้อยที่สุดจาก array ดังกล่าวนี้ (\(1 ≤ arr.length ≤ 2^{100}\))

สำหรับโจทย์นี้สามารถแก้ได้โดย Linear search แต่แนะนำว่าให้ใช้ Binary search ในการแก้ปัญหาเพื่อให้เข้าใจถึงการปรับใช้มากขึ้นและไม่ควรใช้ function sort(arr)

Example 1:

Input: [1, 2, 3, 4, 5]

Output: 1

Example 2:

Input: [4, 5, 6, 2, 3]

Output: 2

Solution #1

สำหรับ naive solution ข้อนี้เราสามารถแก้ได้โดยใช้ linear search (ในการไล่หาค่าที่น้อยที่สุด) แต่จะเห็นว่า arr.length อาจจะมีค่าได้มากถึง \(2^{100}\) ซึ่งเยอะมาก ๆ ถ้าหากเราทำ linear search เราต้อง loop ทั้งหมด \(2^{100}\) ครั้งเลยทีเดียว

Time Complexity: \(O(n)\), Space Complexity: \(O(1)\)

Solution #2

ในข้อนี้ถ้าหากว่าเราลองสังเกต input ดูเราก็จะพบว่าข้อมูลมีทิศทางที่ชัดเจนของมันอยู่ โดยเราสามารถแบ่งข้อมูลออกเป็นเคสหลัก ๆ ได้สองเคสคือ เคสที่ไม่ถูกหมุน และเคสที่ arr ถูกหมุน

Solution #2 - Input Structure
ให้ L แทน left และ R แทน right

จาก Case 1 เราจะพบว่า arr ของเราจะเรียงจากน้อยไปมากอยู่แล้ว (L ≤ R) ดังนั้นค่าที่น้อยที่สุดก็คือค่าด้านซ้ายที่สุดของ arr หรือก็คือค่าแรกสุดนั่นเอง

สำหรับ Case 2 นั้น เราจะพบว่ามีค่าที่น้อยบางส่วนถูกหมุนไปอยู่ด้านหลัง โดยจะสังเกตได้จากว่าค่าเริ่มต้นมีค่ามากกว่าค่าสุดท้าย (L > R) ดังนั้นค่าที่น้อยที่สุดก็จะอยู่ในฝั่งหลังนั้นเอง (หรือถ้าเรามองแค่ฝั่งหลังอย่างเดียว เราอาจจะมองว่ามันเป็น Case 1 ก็ได้)

จากสองเคสข้างต้นนี้เอง ถ้าหากว่าเราสร้างตัวแปรนึงที่ชื่อ M (mid) และลองจิ้มไปสักตำแหน่งหนึ่งใน Case 2 เราก็จะพบว่าเราสามารถบอก direction ได้ว่าเราควรจะย้าย M ไปในทิศทางไหนเพื่อให้เราเข้าไกล้คำตอบมากขึ้นได้ เช่น

Solution #2 - Mid pointer

Case 2.1 จะเห็นว่า M มีค่ามากกว่าค่าสุดท้าย นั่นหมายความว่า arr นี้ถูกหมุนและค่าที่น้อยที่สุดจะอยู่ฝั่งขวา ดังนั้นเราจะเลื่อน M ไปทางฝั่งขวา

Case 2.2. จะเห็นว่า M มีค่าน้อยกว่าค่าสุดท้าย หมายความว่าถ้าเราเลื่อน M ไปฝั่งซ้ายเรื่อย ๆ เราก็จะเจอกับค่าที่น้อยที่สุด

โดยสรุปแล้ว เราสามารถใช้ Binary search ในการหาค่าที่น้อยที่สุดได้ โดยเราก็แค่เช็คว่าถ้า arr[mid] > arr[n-1] เราก็จะย้ายค่า mid ไปหาฝั่งขวา (Case 2.1) ส่วนในทางกลับกัน (Case 2.1) เราก็จะย้าย mid ไปทางฝั่งซ้ายนั่นเอง

1
function findMin(arr) {
2
  const n = arr.length;
3
  let L = 0;
4
  let R = arr.length - 1;
5
  let result = -1;
6


7
  while (L <= R) {
8
    let mid = Math.floor(L + (R - L) / 2);
9


10
    // Condition: Case 2.1
11
    if (arr[mid] > arr[n-1]) {
12
      L = mid + 1;
13
    } else {
14
      // Case 2.2
15
      R = mid - 1;
16
      result = arr[mid];
17
    }
18
  }
19


20
  return result;
21
}

Time Complexity: \(O(log_2n)\), Space Complexity: \(O(1)\)

สำหรับ input size = \(2^{100}\) ถ้าหากเราใช้ binary search เราจะ search และหาคำตอบเจอได้ภายใน 100 ครั้งเท่านั้น

Published: April 10, 2024
Updated: April 10, 2024
Reading time: 20 mins

Table of Content

Contact: [email protected]

© 2024 LearnAlgorithm.com, All rights reserved.

Made with by Chun Rapeepat