Google         youtube            psv            สพม.11

การค้นหาแบบแบ่งครึ่ง 
เทคนิคการค้นหาแบบลำดับทั้งหมดมีการเปรียบเทียบค่าเท่ากับ O(n)  เมื่อปรับปรุงประสิทธิภาพโดยใช้วิธีต่าง ๆ ที่กล่าวมาก็ยังคงเป็น  O(n)  เช่นเดิม  ซึ่งเป็นการค้นหาแบบเชิงเส้นแต่มีเทคนิคในการปรับปรุงประสิทธิภาพที่ไม่ใช่ แบบเชิงเส้น  โดยใช้โครงสร้างข้อมูลไบนารี่ทรี  (Binary Tree)  ซึ่งในกรณีเฉลี่ย  การค้นหาจะเท่ากับ  O  (log2 n)  ขณะที่แบบเชิงเส้นจะเท่ากับ O  (n/2)  จะเห็นว่าถ้า n มีค่ามาก ๆ การค้นหาแบบไบนารี่ทรีจะยิ่งมีประสิทธิภาพมากกว่าแบบเชิงเส้น
เทคนิคการค้นหาแบบแบ่งครึ่งสามารถใช้กับข้อมูลที่อยู่ในรายการแบบเชิงเส้น เช่นเดียวกับใช้ในไบนารี่ทรี  แต่ต้องมีการจัดเรียงตามลำดับค่าของคีย์ก่อน  และทราบจำนวนเรคคอร์ดทั้งหมด  การค้นหาจะทำการตรวจสอบค่าที่อยู่ในรายการ  โดยการตรวจสอบครั้งแรกเริ่มต้นเปรียบเทียบค่าของคีย์ที่อยู่ในตำแหน่งตรง กลางกับค่าที่ค้นหา  หากพบว่าค่าที่ค้นหาน้อยกว่าก็จะไปค้นหาต่อยังส่วนหลังที่เหลือครึ่งหนึ่ง  แต่ถ้าพบว่ามากกว่าก็ไปค้นหาต่อยังส่วนต้นที่เหลือครึ่งหนึ่ง  เมื่อตรวจสอบครั้งที่สองจะเปรียบเทียบค่าของคีย์ที่อยู่ตำแหน่งตรงกลางของ ส่วนที่เหลือครึ่งหนึ่ง  ถ้ายังไม่พบก็ทำการแบ่งครึ่งหนึ่งไปเรื่อย ๆ เช่นเดียวกับที่ผ่านมาจนกว่าจะพบหรือไม่พบเมื่อไม่สามารถแบ่งครึ่งได้อีก  ดังในรูปที่ 12.3  ซึ่งเป็นการแสดงขั้นตอนการตรวจสอบค้นหาค่า 72 ของคีย์ที่ต้องการในรายการแบบเชิงเส้น  โดยเริ่มต้นมีคีย์ทั้งหมด 16 ค่า

3

5

9

24

15

63

66

68

70

72

73

81

84

90

91

93


ตรวจสอบ # 1

70

72

73

81

84

90

91

93


ตรวจสอบ # 2

70

72

73


ตรวจสอบ # 3

รูปที่ 12.3  การค้นหาค่าของคีย์แบบแบ่งครึ่ง

                           –    การตรวจสอบครั้งแรกไปยังตำแหน่งตรงกลาง คือ 8 (16/2)  ได้ค่าของคีย์  คือ 68 เมื่อเปรียบเทียบกับค่าที่หาได้พบว่า 68 < 72  จึงไปค้นหาต่อยังครึ่งหลังที่เหลือจากตรงกลาง
–    การตรวจสอบครั้งที่สองไปยังตำแหน่งตรงกลางของส่วนที่เหลือ คือ 12 ((8+16)/2)  ค่าของคีย์  คือ 81  เปรียบเทียบกันได้ 81 > 72  จึงไปค้นหาต่อยังครึ่งตอนต้นของส่วนที่เหลือ
–    การตรวจสอบครั้งที่สามไปยังตำแหน่งตรงกลางของส่วนที่เหลือ คือ 10  ((8+12)/12)  ค่าของคีย์ได้เป็น 72 เปรียบเทียบกันแล้วเท่ากัน  จึงพบค่าของคีย์ที่ค้นหา
จากตัวอย่างพบว่าการตรวจสอบและเปรียบเทียบค่ามีเพียง 3 ครั้ง  ขณะที่ใช้การค้นหาแบบลำดับมีถึง 10 ครั้ง  การค้นหาจะแบ่งครึ่งไปเรื่อย ๆ จนแบ่งไม่ได้จึงทราบว่าค่าที่ต้องการหาไม่มีในรายการ  และการค้นหาแบบแบ่งครึ่งจะใช้อัลกอริทึมแบบวนลูป (Iterative)  หรือใช้แบบรีเคอร์ซีฟ (Recursive)  ก็ได้  สำหรับอัลกอริทึมแบบวนลูปดังในตารางที่ 12.3
ตารางที่ 12.3  อัลกอริทึมการค้นหาแบบแบ่งครึ่ง 

1.  ให้ low = 0  และ high = n-1
2.  ทำขั้นตอน 3-5 ซ้ำ  ถ้า low £ high
3.  ให้ mid = (low+high)/2
4.  ถ้าค่า a mid ในอาร์เรย์เท่ากับค่า k ที่ค้นหา  ให้ส่งค่า mid กลับมา
5.  ถ้าค่า a mid < k ให้  low = mid + 1  ไม่เช่นนั้นให้ high = mid-1
6.  ไม่พบส่งค่า -1 กลับมา

และเขียนเป็นฟังก์ชันการค้นหาแบบแบ่งครึ่งได้เป็นตารางที่ 12.4

ตารางที่ 12.4  ฟังก์ชันการค้นหาแบบแบ่งครึ่ง 
Int binarySearch (int key[],int size, int value){
Int low=0;
Int high=size-1;
Int mid;
While(low<=high){
mid=(low+high)/2;
if(key[mid]>value)
high=mid-1;
else if(key[mid]<value)
low=mid+1;
else
return mid;
}
Return-1;
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s