ผู้ใช้:Pantarut/แบบร่างบทความ

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

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

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

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

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

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

ตัวอย่าง แก้

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

นี่คือเกมพื้นฐานที่ใช้หลักการเดียวกันกับขั้นตอนวิธีนี้โดยเริ่มจากคำพูดว่า "ผมกำหนดจำนวนเต็มหนึ่งจำนวนที่มีค่าระหว่าง 40 ถึง 60 และเพื่อที่คุณจะเดาได้ ผมจะบอกว่า 'มากกว่า', 'น้อยกว่า' หรือ 'ใช่!' เมื่อคำตอบถูกต้อง" การค้นหาข้อมูลจำนวน "N" ข้อมูลที่เป็นไปได้ดังนั้นมากกว่า $\lfloor \log _{2}N\rfloor$ คำถามที่ต้องถาม หรือกล่าวง่ายๆว่าเกมจะต้องกำหนดจำนวนคำถามมากกว่า $\lfloor \log _{2}N\rfloor$ คำถาม เมื่อมีการถามแต่ละครั้งพื้นที่ในการค้นหาแต่ละครั้งก็จะถูกแบ่งครึ่งไปเรื่อยๆ ดังนั้นจำนวนการค้นหาจึงถูกบีบให้อยู่ในช่วงๆหนึ่ง แม้ว่าจำนวนที่จะเดามีขนาดใหญ่ก็ตาม, ในกรณีที่ไม่มีขอบเขตบนก็จะสามารถค้นหาได้ที่ประสิทธิภาพ $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 ครั้งสำหรับการค้นหาแบบทวิภาค แต่อย่างไรก็ตามการค้นหาแบบทวิภาคก็ต้องค้นหาได้ในเพียงแถวลำดับที่มีการเรียงลำดับแล้ว

อ้างอิง แก้

รูปภาพ แก้

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)