สวัสดีค่ะเพื่อน ๆ ทุกคน วันนี้โซวอนจะพาเพื่อน ๆ ไปทำ Binary Search Algorithm กัน โซวอนว่าการที่เพื่อน ๆ เข้ามาที่บทความนี้ได้ คงรู้จักกันบ้างแล้วว่า Binary Search Algorithm คืออะไร แต่ถ้าใครยังไม่รู้ เดี๋ยวโซวอนจะแนะนำคร่าว ๆ แล้วกัน ก่อนที่เราจะมาเริ่มทำ Binary Search Algorithm กันBinary Search Algorithm คือ การค้นหาประเภทหนึ่งที่อยู่ใน Linear Searching Algorithm แล้วตัว Linear Searching Algorithm ที่ว่านี่มันคืออะไรละ Linear Searching Algorithm เป็นขั้นตอนวิธีในการค้นหาข้อมูล โดยนํา Target (ข้อมูลที่ต้องการ) มาเปรียบเทียบกับข้อมูลที่เก็บอยู่ในโครงสร้างข้อมูลไล่ไปเรื่อย ๆ ทีละตัวว่าตรงกันหรือไม่แล้วตัว Binary Search Algorithm ที่ว่านี้มันมีประโยชน์ยังไงล่ะ สมมติเลยนะว่า ถ้าเรามีของหลายชิ้นมาก ๆ และอยากหาของสิ่งหนึ่งว่าอยู่ในนั้นไหม สิ่งแรกที่เราจะทำกันก็คือมองหาทั่ว ๆ การหาสะเปะสะปะ เป็นวิธีที่ง่ายก็จริงแต่เสียเวลามาก แต่ถ้าเรานำสิ่งของมาเรียงกันแล้วค่อย ๆ หาไปทีละครึ่งแล้วตรวจสอบว่ามันมีไหม ถ้าครึ่งนี้ไม่มีก็ไปหาอีกครึ่งหนึ่ง มันจะเร็วกว่าไหมนั้นแหละ คือหลักการทำงานของ Binary Search Algorithm มันเป็นประโยชน์อย่างมาก เพราะมันรวดเร็ว หลายระบบ หลายเว็บไซต์ จึงเลือกใช้ Binary Search Algorithm เพื่อจัดการข้อมูลที่มากมาย แต่ถ้าใครไม่ได้เขียนโปรแกรมก็สามารถนำหลักการการหาข้อมูลแบบนี้ไปใช้ในชีวิตประจำวันได้นะ เช่นถ้าเพื่อน ๆ ต้องการหาหนังสือที่เพื่อน ๆ ต้องการในร้านหนังสือ เพื่อน ๆ ก็แค่หาไปทีละครึ่งแถวว่ามันมีหนังสือที่เราต้องการไหม มันจะช่วยเพิ่มความเร็วในการค้นหาเลยล่ะ++ ++ เอาล่ะ น่าจะพอนึกภาพออกกันบ้างแล้ว โซวอนว่าเรามาดูหลักการทำงานของ Binary search กันเลยดีกว่า หลักการทํางานของ Binary Search คือ เปรียบเทียบข้อมูลที่ต้องการค้นหา (Target) กับข้อมูลตัวตรงกลาง (Mid) ในโครงสร้างข้อมูลว่าตรงกันใช่หรือไม่ - ถ้าไม่ใช่ ให้พิจารณาว่า Target มีค่ามากกว่าหรือน้อยกว่า Mid - ถ้า Target มีค่าน้อยกว่า Mid จะไม่พิจารณาข้อมูลในโครงสร้างข้อมูลครึ่งหลัง (นั่นคือ ข้อมูลทั้งหมดตั้งแต่ Mid ไปจนถึงข้อมูลที่อยู่ในตําแหน่งสุดท้าย) ให้ตัดทิ้งไปได้เลย - ถ้า Target มีค่ามากกว่า Mid จะไม่พิจารณาข้อมูลในโครงสร้างข้อมูลครึ่งหน้า (นั่นคือ ข้อมูลทั้งหมดตั้งแต่ตําแหน่งแรกจนถึงข้อมูลในตําแหน่ง Mid) ให้ตัดทิ้งไปได้เลยเช่นกัน -จากนั้นให้หา Mid ตัวใหม่ของโครงสร้างข้อมูลส่วนที่ยังเก็บไว้ (ส่วนที่เก็บไว้พิจารณาไม่ได้ตัดทิ้ง) เพื่อเปรียบเทียบต่อไป ทําเช่นนี้ไปเรื่อยๆ จนกว่าจะพบหรือจะหมดข้อมูล (นั่นคือ ไม่สามารถแบ่ง listข้อมูลให้เล็กลงได้อีกแล้ว) !!เอ๊ะ!! แต่เดี๋ยวก่อน ก่อนที่เพื่อน ๆ จะมาพิจารณาหลักการข้างบนได้ สิ่งที่ต้องทำก่อนคือการ sorting หรือเรียงลำดับข้อมูล อย่าลืมทำนะคะ ไม่งั้นเขาไม่เรียก Binary Search Algorithm นะคะ ~_~จากหลักการข้างบนเลยเพื่อน ๆ คงสงสัยกันว่า เเล้วค่า mid ที่ว่านี่มันหายังไงละการหา mid หรือตำแหน่งกึ่งกลาง สิ่งที่เราต้องทำ คือกําหนดให้ - Low แทนตําแหน่ง (Index) ของค่าต่ำสุด - Mid แทนตําแหน่ง (Index) ของค่ากึ่งกลาง - High/Upper แทนตําแหน่ง (Index) ของค่าสูงสุดของ list ที่กําลังพิจารณาสูตรคํานวณ Mid คือ Mid = [ low + upper ] / 2ค่า Mid คือค่า floor (จํานวนเต็มที่มากที่สุดที่น้อยกว่า [ low + upper ] / 2 )ค่า floor ตัวอย่างเช่น 4.5 ค่า floor เท่ากับ 4 หรือ 9.5 ค่า floor เท่ากับ 9ตัวอย่างการหาค่า mid(รูปภาพโดย SONE4EVA) วิธีการทำLow = 0, Upper = 7 ดังนั้น Mid = ( 0 +7 ) / 2 = 3 นั่นคือ Mid จะเท่ากับ Index ที่ 3 ของ list (ค่า Mid คือ 8)หลังจากที่เรารู้หลักการการหาต่างๆแล้ว งั้นเราก็มาลองทำโจทย์กันดูบ้างดีกว่า ** โจทย์ **จงแสดงการค้นหาข้อมูลด้วย Binary Search Algorithm เพื่อค้นหาข้อมูลที่ต้องการ (Target) คือ 19 จากชุด ข้อมูลต่อไปนี้ 1 12 3 8 6 19 5 10 12 13 22 16 18 7 20 15มาเริ่มทำกัน สิ่งแรกที่เราต้องทำคือ sorting ข้อมูลเรียงลำดับข้อมูลจากน้อยไปมาก ได้ข้อมูลเป็น 1 2 3 5 6 7 8 10 12 13 15 16 18 19 20 22(รูปภาพโดย SONE4EVA) Mid = ( 0+15 ) / 2 = 7.5ดังนั้น ค่า Mid = 7 ในindex 7 มีค่าเท่ากับ 10 เปรียบเทียบค่า target ซึ่ง 19>10 ดังนั้นหาข้อมูลฝั่งขวาต่อ(รูปภาพโดย SONE4EVA) Mid = ( 8+15 ) / 2 = 11.5ดังนั้น ค่า Mid = 11 ในindex 11 มีค่าเท่ากับ 16 เปรียบเทียบค่า target ซึ่ง 19>16 ดังนั้นหาข้อมูลฝั่งขวาต่อ(รูปภาพโดย SONE4EVA) Mid = ( 12+15 ) / 2 = 13.5ดังนั้น ค่า Mid = 13 ในindex 13 มีค่าเท่ากับ 19 ซึ่ง 19 เท่ากับค่า target ที่ต้องการ ++ เจอแล้ว ++ ทั้งหมดนี้ก็เป็นวิธีการทำ Binary Search Algorithm ง่ายมากใช่ไหมละ โซวอนหวังว่าบทความนี้จะช่วยให้เพื่อน ๆ มีความเข้าใจเรื่อง Binary Search Algorithm มากขึ้นนะคะ เดี๋ยวบทความต่อไปจะพาไปรู้จัก Search Algorithm ตัวอื่นกันบ้าง ~_~