อ่านบทความนี้ใน Facebook
เรามักจะได้ยินมาว่า binary search ใช้ได้ก็ต่อเมื่อข้อมูลถูก sorted เท่านั้น; หรือข้อมูลต้องเรียงไม่จากน้อยไปมาก ก็มากไปน้อยมาก่อน
แต่คำถามคือ “ทำไมข้อมูลถึงต้อง sorted หละ!?”
เราก็อาจจะตอบว่า เพราะถ้าเราสุ่มไปที่ position ใดในข้อมูลนึง มันทำให้เรา “รู้ทิศทาง” ว่าเราจะต้องไปหา target element ที่เราตามหาต่อในทิศทางไหน (ฝั่งซ้ายหรือฝั่งขวา)
ลองนึกภาพว่าอยากเปิดหนังสือหน้า 50 แต่สุ่มเปิดมาเจอหน้า 25 เราก็ต้องสุ่มเปิดครึ่งหลังของหนังสือต่อใช่ไหมครับ; เพราะเรารู้อยู่แล้วว่าเลขหน้ามันเรียงจากน้อยไปมาก และสิ่งนี้มันบอกเราว่าถ้าอยากเจอหน้า 50 ก็ไปหาต่อครึ่งหลังสิ
จากตรงนี้เราอาจจะพอเห็นได้ว่า ณ จุดใดจุดหนึ่งของข้อมูล
ถ้าเรารู้ทิศทางข้อมูลว่า “ทิศไหนมันช่วยให้เราเข้าใกล้คำตอบได้มากขึ้น” เราก็สามารถจะตัด choice และค่อย ๆ เข้าใกล้สู่คำตอบไปเรื่อย ๆ ได้
ลองคิดเล่น ๆ ว่าถ้าเรามีข้อมูลที่ “เรียงจากน้อยไปมาก แต่พอไปถึงจุดหนึ่งจะเรียงจากมากไปน้อย” (ดังรูปตัวอย่าง) ถ้าเราต้องหา peak element จาก array ดังกล่าว เราสามารถใช้ binary search ในการหาได้ไหม?
คำตอบก็คือได้ครับ! ถ้าเราลองสุ่มจิ้มไปที่ element สักตัว เราก็แค่เช็คตัวถัดไปที่อยู่ติดกันเพื่อดูว่าตอนนี้เรา “กำลังขึ้นเขา” หรือ “กำลังลงเขา”
- ถ้ากำลังขึ้นเขา ก็แสดงว่า peak อยู่ในฝั่งขวาของ array
- ถ้ากำลังลงเขา ก็แสดงว่า peak อยู่ในฝั่งซ้ายของ array นั่นเอง
จะเห็นว่า array ดังกล่าวไม่ได้ sorted (ถ้านิยามของการ sort คือการจัดเรียงใน ascending และ descending) แต่ถูก ordered ผ่านกฏเกณฑ์บางอย่างที่มันบอก “ทิศทางของข้อมูล” ที่ทำให้เราสามารถตัด choice เพื่อทำให้เข้าใกล้คำตอบได้มากขึ้น
อีกตัวอย่างนึงก็ rotated sorted array ที่สามารถใช้ binary search ในการหาข้อมูลได้เช่นกัน
ส่วนตัวเรามองว่า พอเราได้ยินหรือเห็นตัวอย่างตอนเรียนว่าจะได้ binary search ได้ข้อมูลจะต้องเรียงจากน้อยไปมาก หรือมากไปน้อยเท่านั้น มันทำให้บางครั้งเราตัดความเป็นไปได้ที่จะใช้ binary search ออกไปเวลาเจอข้อมูลที่มันไม่ตรงกับที่เราคิด
เรามองว่าโจทย์นี้เป็นตัวอย่างที่ดีเลยที่ทำให้เรากลับมาตั้งคำถามกับ binary search ให้มากขึ้น และเห็น application ที่กว้างขึ้นเวลาที่เราจะเลือกหยิบ binary search มาใช้งาน
