การค้นหาแบบทวิภาค

ในสาขาวิทยาการคอมพิวเตอร์ การค้นหาแบบทวิภาค (อังกฤษ: binary search, half-interval search หรือ bisection search) เป็นขั้นตอนวิธีเพื่อหาตำแหน่งของค่าที่ต้องการ (ข้อมูลนำเข้า หรือ "key") ที่ใช้ในแถวลำดับที่ได้มีการเรียงลำดับข้อมูลแล้ว ขั้นตอนวิธีจะเริ่มจากเปรียบเทียบข้อมูลที่นำเข้ากับข้อมูลที่อยู่ตรงกลางของแถวลำดับ ถ้าข้อมูลมีค่าเท่ากันแสดงว่าพบ "คีย์" ที่ต้องการ อาจจะทำการคืนค่าตำแหน่งหรือในที่นี้คือ ดัชนี (index) กลับไป มิฉะนั้นถ้าค่าของข้อมูลนำเข้าที่ต้องการค้นหามีการน้อยกว่าค่าตรงกลางของแถวลำดับ ก็จะทำขั้นตอนวิธีนี้อีกครั้งแต่เปลี่ยนมาค้นหาในแถวลำดับย่อยของแถวลำดับที่ต้องการค้นหาโดยแถวลำดับย่อยจะมีจุดสิ้นสุดที่ตรงกลางของแถวลำดับหลัก หรือถ้าข้อมูลที่ต้องการค้นหามีค่ามากกว่าแล้วจะค้นหาในแถวลำดับย่อยเช่นกันแต่ย้ายจุดเริ่มต้นมาที่ตรงกลางของแถวลำดับหลัก เมื่อทำไปจนแถวลำดับไม่มีสมาชิกอยู่หรือจุดเริ่มต้นมากกว่าจุดสิ้นสุด แสดงว่าไม่มีสมาชิกในแถวลำดับตัวใดที่มีค่าเท่ากับข้อมูลนำเข้าที่ต้องการค้นหา อาจจะคืนค่าว่า "ไม่พบ"

การค้นหาแบบทวิภาค

ประเภท	ขั้นตอนวิธีการค้นหา
โครงสร้างข้อมูล	แถวลำดับ
ประสิทธิภาพเมื่อเกิดกรณีแย่ที่สุด	${\displaystyle O(\log n)}$
ประสิทธิภาพเมื่อเกิดกรณีดีที่สุด	${\displaystyle O(1)}$
ประสิทธิภาพเมื่อเกิดกรณีทั่วไป	${\displaystyle O(\log n)}$
ปริมาณความต้องการพื้นที่เมื่อเกิดกรณีแย่ที่สุด	${\displaystyle O(1)}$
ด ค ก

การค้นหาแบบทวิภาคจะแบ่งครึ่งชุดข้อมูลที่ต้องการค้นหา ดังนั้นจึงจัดให้การค้นหาแบบทวิภาคเป็นขั้นตอนวิธีแบ่งแยกและเอาชนะ และขั้นตอนวิธีการค้นหา

การใช้ในงานทั่วไป

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

ถ้ารายการที่ได้ค้นหามีข้อมูลเล็กน้อยเช่น 1โหล การค้นหาแบบทวิภาคจะใช่เวลาเพียงเล็กน้อยเมื่อเปรียบเทียบกับการค้นหาแบบเชิงเส้น แต่มันต้องการรายการที่มีการเรียงลำดับมาแล้ว คล้ายกับตารางแฮชหรือการค้นหาแบบแฮชที่มีความเร็วมากกว่าการค้นหาแบบทวิภาคแต่ยังมีลักษณะของข้อมูลที่ค่อนข้างเจาะจงกว่าด้วยเช่นกัน ถ้ารู้ว่าต้องทำการค้นหาเป็นจำนวนหลายครั้งหรือลักษณะของข้อมูลตรงกับที่ต้องการแล้วควรเลือกใช้การค้นหาแบบทวิภาค แต่ถ้าต้องค้นหาเพียงไม่ก็ครั้งหรือเพียงครั้งเดียวการเลือกใช้การค้นหาแบบเชิงเส้นก็น่าจะเป็นตัวเลือกที่ดีที่สุด

ตัวอย่าง

เกมเดาตัวเลข

นี่คือเกมพื้นฐานที่ใช้หลักการเดียวกันกับขั้นตอนวิธีนี้โดยเริ่มจากคำพูดว่า "ผมกำหนดจำนวนเต็มหนึ่งจำนวนที่มีค่าระหว่าง 40 ถึง 60 และเพื่อที่คุณจะเดาได้ ผมจะบอกว่า 'มากกว่า', 'น้อยกว่า' หรือ 'ใช่!' เมื่อคำตอบถูกต้อง" การค้นหาข้อมูลจำนวน "N" ข้อมูลที่เป็นไปได้ดังนั้นมากกว่า ${\displaystyle \lfloor \log _{2}N\rfloor }$  คำถามที่ต้องถาม หรือกล่าวง่ายๆว่าเกมจะต้องกำหนดจำนวนคำถามมากกว่า ${\displaystyle \lfloor \log _{2}N\rfloor }$  คำถาม เมื่อมีการถามแต่ละครั้งพื้นที่ในการค้นหาแต่ละครั้งก็จะถูกแบ่งครึ่งไปเรื่อยๆ ดังนั้นจำนวนการค้นหาจึงถูกบีบให้อยู่ในช่วงๆหนึ่ง แม้ว่าจำนวนที่จะเดามีขนาดใหญ่ก็ตาม, ในกรณีที่ไม่มีขอบเขตบนก็จะสามารถค้นหาได้ที่ประสิทธิภาพ ${\displaystyle 2\lfloor \log _{2}k\rfloor +1}$  เริ่มด้วยหาขอบเขตบนโดยการเพิ่มค่าที่เดาซ้ำแล้วซ้ำอีก ตัวอย่างเช่น คำตอบคือ 11 โดยจะเดาเป็นแบบรูปดังนี้ 1(มากกว่า), 2(มากกว่า), 4(มากกว่า), 8(มากกว่า), 16(น้อยกว่า), 12(น้อยกว่า), 10(มากกว่า) และนี่เรารู้ว่าจำนวนนั้นคือ 11 เพราะเป็นจำนวนที่มากกว่า 10 และน้อยกว่า 12 ถ้าลองใช้วิธีการนี้กับจำนวนเต็มลบและศูนย์บ้าง เช่น จะหา −13: 0, −1, −2, −4, −8, −16, −12, −14 ในที่สุดแล้วก็จะรู้ว่าเลขที่ต้องการคือ -13 เพราะเป็นเลขที่น้อยกว่า -12 และมากกว่า -14

รายการของคำ

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

ขั้นตอนวิธี

แบบเวียนเกิด

การค้นหาแบบทวิภาคสามารถใช้การเรียกซ้ำได้ โดยมีสิ่งที่ต้องการคือพารามิเตอร์อันได้แก่ แถวลำดับที่มีการเรียงลำดับมากแล้ว(ในต้วอย่างจะเป็นการเรียงลำดับจากน้อยไปมาก) และแน่นอนว่าต้องสามารถอ้างถึงแถวลำดับตรงการด้วยดัชนี(index)ต้นและปลายของแถวลำดับ ซึ่งพารามิเตอร์เหล่านี้จะทำให้สามารถเรียกฟังก์ชันแบบเรียกซ้ำได้ และโดยขั้นตอนวิธีแล้ว การเขียนการค้นหาแบบทวิภาคด้วยการเวียนเกิดหรือเรียกซ้ำนั้นคอมไพเลอร์จะไม่มีการสร้างกองซ้อนกองใหม่ขึ้นมาโดยจะใช้เพียงกองเดียวเท่านั้น พิจารณาที่ตัวแปร a คือแถวลำดับที่ต้องการค้นหา key คือค่าของตัวแปรที่ต้องการค้นหาในแถวลำดับ a left คือดัชนีของต้นแถวลำดับ a และ right คือดัชนีของปลายแถวลำดับ a

int binary_search(int a[], int key, int left, int right) { if(left > right) //ถ้าค่าของ left มากกว่า right แสดงว่าแถวลำดับย่อยไม่มีสมาชิกเหลืออยู่แล้ว และไม่มี key ที่ต้องการ return -1; //คืนค่าที่ต้องการแสดงว่าไม่พบค่า key else //ถ้ายังมีสมาชิกอยู่ก็ทำการค้นหาต่อไป { int mid = (left+right)/2; //mid ดัชนีตรงกลางของแถวลำดับย่อยหรือหลัก if(a[mid]>key) //ถ้าค่าตรงกลางของแถวลำมีค่ามากกว่า key แสดงว่า key ต้องอยู่ระหว่าง a[left] กับ a[mid-1]  return binary_search(a,key,left,mid-1); //ดังนั้นจึงไปค้นหาต่อในแถวลำดับย่อยระหว่าง left และ mid-1 if(a[mid]<key) //ในทำนองเดียวกันกับ ค่าตรงกลางของแถวลำมีค่ามากกว่า key  return binary_search(a,key,mid+1,right); if(a[mid]==key) //หากค่าตรงการของแถวลำกับมีค่าเท่ากับ key แสดงว่าพบแล้ว  return mid; //คืนค่าตำแหน่งของ key ในแถวลำดับ a กลับไป } } 

โดยจะให้ค่าของ left เท่ากับ 0 และ right เท่ากับ N-1 สำหรับแถวลำดับที่มีจุดเริ่มที่ศูนย์และมีสมาชิก N ตัว ดังนั้นเราจึงได้ค่าของ mid หรือ ดัชนีที่ชี้ตรงกลางของแถวลำดับที่เริ่มต้นที่ left ถึง right นั่นคือจะมีค่าเท่ากับ (left+right)/2

การวนซ้ำ

การค้นหาแบบทวิภาคยังสามารถในแบบการวนซ้ำได้เนี่องจากการค้นหาแบบนี้มีการทำงานเป็นเชิงเส้นไม่ได้มีการแตกการทำงานแต่อย่างใด

int binary_search(int a[], int key, int left, int right) {  while (left <= right)  {  int mid = (left+right)/2;  if (a[mid] < key)  left = mid + 1;  else if (a[mid] > key)  right = mid - 1;  else //พบ key ในแถวลำดับ a แล้ว  return mid;  }  // ไม่พบ key  return -1; } 

ประสิทธิภาพ

ในแต่ละการทดสอบที่ล้มเหลวในการค้นหาจำนวนที่มีค่าตรงกันจะเป็นกรณีที่มีจำนวนการทำงานมากที่สุด โดยถ้า "N" เป็นจำนวนคี่จะแบ่งช่วงย่อยเป็น ("N"-1)/2 และถ้าเป็นจำนวนคู่จะแบ่งเป็นช่วงละ "N"/2-1 และ "N"/2

ถ้าจำนวนแถวลำดับตอนเริ่มต้นเท่ากับ "N" จะถูกแบ่งเป็นประมาณ "N"/2 แล้วแบ่งเป็น "N"/4 แล้วเป็น "N"/8 ไปเรื่อยๆ โดยในกรณีที่แย่ที่สุดเกิดเมื่อค่าที่ต้องการไม่อยู่ในแถวลำดับ จะทำการคำนวณ ⌊log₂(N)+1⌋ ครั้ง เมื่อเราเปรียบเทียบกับการค้นหาเชิงเส้น พฤติกรรมการทำงานของกรณีแย่ที่สุดของแต่ะมันจะเป็น "N" เราจะเห็นได้ว่าการค้นหาแบบทวิภาคจะเร็วกว่าในกรณีที่ความยาวของแถวลำดับเป็น "N" ยกตัวอย่างเช่น ถ้าจะค้นหาในรายการที่มีจำนวนสมาชิกล้านตัวมันจะทำการวนซ้ำประมาณล้านรอบสำหรับการค้นหาแบบเชิงเส้น แต่มันจะไม่มากกว่า 20 ครั้งสำหรับการค้นหาแบบทวิภาค แต่อย่างไรก็ตามการค้นหาแบบทวิภาคก็ต้องค้นหาได้ในเพียงแถวลำดับที่มีการเรียงลำดับแล้ว

อ้างอิง

1. Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. (1990). Introduction to Algorithms (1st ed.). MIT Press and McGraw-Hill. ISBN 0-262-03141-8.
2. เอริก ดับเบิลยู. ไวส์สไตน์, "Binary Search" จากแมทเวิลด์.
3. Press, William H.; Flannery, Brian P.; Teukolsky, Saul A.; Vetterling, William T. (1988), Numerical Recipes in C: The Art of Scientific Computing, Cambridge University Press, pp. 98–99, ISBN 0-521-35465-X

รูปภาพ

• http://www.eexploria.com/wp-content/uploads/2012/04/binary-search-program-shell.gif

โค้ดอื่นๆ

• Kruse, Robert L.: "Data Structures and Program Design in C++", Prentice-Hall, 1999, ISBN 0-13-768995-0, page 280.
• van Gasteren, Netty; Feijen, Wim (1995). "The Binary Search Revisited" (PDF). AvG127/WF214. (investigates the foundations of the binary search, debunking the myth that it applies only to sorted arrays)

การเชื่อมโยงภายนอก

• NIST Dictionary of Algorithms and Data Structures: binary search
• Binary search implemented in 12 languages