First and last x in sorted array ( leetcode writeup )
โจทย์ดังรูป
เพื่อให้เขียนง่ายขึ้น และเน้นไปที่ algorithm เราจะเขียน function เลย โดยข้ามการรับ input ไปเนอะ
เอาละ มาลองทำกัน เราจะเริ่มจากวิธีเบสิคที่สุดก่อน
ซึ่งวิธีนี้มี time complexity = O(n) เกินจากที่โจทย์กำหนด O(logn) เลยใช้ไม่ได้
โอเค เรามาวิเคราะห์โจทย์กันใหม่ โจทย์ให้หา 2 อย่างคือ
1 ตำแหน่งแรกของเลขที่ต้องการ
2 ตำแหน่งสุดท้ายของเลขที่ต้องการ
โดย input sort มาแล้ว และต้องหาใน O(logn)
… ซึ่ง การหาเลขที่ต้องการจาก array ที่ sort มาแล้วใน O(logn) เนี่ย เราสามารถใช้ binary search ได้ใช่ปะ งั้นมาลองเขียน binary search กันก่อน
ทีนี้จาก code binary search ด้านบน เนี่ย สมมุติว่าเราจะหา 8 จาก 5 7 7 8 8 10 ก็จะเจอ 8 ตัวที่สองเป็นตัวแรกแล้วหยุดการหาเนอะ … แล้วถ้าเราหา 8 ตัวต่อไปเรื่อยๆ โดยไม่หยุดละ ? เช่น เราบอกว่าถึงเจอ 8 แล้ว ก็ให้ไปหาทางซ้ายต่อเป็นต้น … แสดงว่า 8 ตัวสุดท้ายที่เราเจอ จะเป็นตัวซ้ายสุด เสมอ = เราสามารถหา 8 ตัวแรกได้แล้วนั่นเอง
และแน่นอนว่าถ้าเราหาไปทางขวาเรื่อยๆ แม้ว่าจะเจอเลขนั้นๆแล้ว … เราจะได้ตำแหน่งของเลขนั้นที่อยู่ขวาสุดมาเช่นกัน
ดังนั้น พอใช้ 2 ฟังก์ชันนี้คู่กัน ก็หาสามารถหาตำแหน่งแรก และสุดท้ายของ x ใน sorted array ด้วยเวลา O(logn) ได้นั่นเอง
