การค้นหาโดยการประมาณช่วง

การค้นโดยการประมาณช่วง (อังกฤษ: Interpolation search) หรือในบางครั้งเรียกว่า การค้นโดยการคาดการณ์ (อังกฤษ: Predictive search, Extrapolation search) เป็นขั้นตอนวิธี (algorithm) สำหรับค้นหาค่าของคำหลัก (key value) ที่ได้รับ(อาจได้รับจากการพิมพ์) โดยทำการค้นหาจาก ดัชนีแถวลำดับหนึ่งๆที่ถูกจัดเรียงอย่างมีระเบียบแบบแผนแล้ว ซึ่งวิธีนี้คล้ายกับวิธีที่เราค้นหา รายชื่อในสมุดโทรศัพท์ของโทรศัพท์มือถือ

ในการค้นหาแต่ละขั้นตอนจะมีการคำนวณหรือ คาดการณ์ว่าสิ่งที่ค้นหานั้น น่าจะอยู่ที่ไหนของช่วงการค้นหาที่เหลือ แม้เทคนิคนี้จะมีลักษณะคล้ายกับการค้นแบบทวิภาค (Binary search) แต่ก็ไม่ใช่เสียทีเดียว ยกตัวอย่างเช่น การค้นหาหมายเลขโทรศัพท์ของนายสมชาย จะไม่ไปหาที่ตรงกลางของสมุดโทรศัพท์ แต่จะไปหายังตำแหน่งที่เริ่มต้นด้วยตัว “ส” โดยการประมาณว่าอยู่ที่ตรงหน้าที่เท่าไรของสมุดโทรศัพท์ แล้วค่อย ๆ เลือกหน้าต่อไปที่ใกล้เคียงที่สุดจนกว่าจะพบ ดังนั้น แทนที่จะใช้การค้นแบบทวิภาค (Binary search) ที่เริ่มต้นตรงกลางเสมอ ก็เปลี่ยนมาใช้การค้นโดยการประมาณช่วง (Interpolation Search) ซึ่งเป็นการค้นหาตำแหน่งโดยการประมาณ

ขั้นตอนวิธี

ดังที่ได้อธิบายลักษณะการทำงานไปบ้างแล้ว การค้นโดยการประมาณช่วง (Interpolation Search) นี้อาศัยการคำนวณตำแหน่งที่น่าจะเป็นตำแหน่งของค่าคำหลักในแถวลำดับหนึ่งๆที่ถูกจัดเรียงเรียบร้อยแล้ว ซึ่งคำนวณจากค่าของคำหลักที่ต้องการค้นหา และ ค่าขอบบน ค่าขอบล่าง ของช่วงการค้นหาช่วงหนึ่ง จาก ช่วงการค้นหาทั้งหมด ซึ่งเราสามารถลดขนาดของช่วงการค้นหาที่เหลือได้ โดยการปรับเปลี่ยน ค่าขอบบน หรือค่าขอบล่างไปเรื่อยๆ จนกว่าจะพบ ค่าที่ต้องกาค้นหา

กำหนดให้

• $low$ หมายถึง ค่าขอบล่าง
• $mid$ หมายถึง ค่ากึ่งกลาง
• $high$ หมายถึง ค่าขอบบน
• $Array[low]$ หมายถึง ค่าของแถวลำดับ ณ ตำแหน่งขอบล่าง
• $Array[mid]$ หมายถึง ค่าของแถวลำดับ ณ ตำแหน่งตามค่ากึ่งกลาง
• $Array[high]$ หมายถึง ค่าของแถวลำดับ ณ ตำแหน่งขอบบน
• $toFind$ หมายถึง ค่าที่ต้องการค้นหา

โดยมีขั้นตอนการทำงานดังนี้

1. เริ่มต้นให้ $low=0$ และ $high=$ ขนาดของแถวลำดับ $-1$
2. เริ่มการทำงานแบบวงวนด้วยเงื่อนไข $Array[low]\leq toFind$ และ $Array[high]\geq tofind$
3. หาค่า $mid$ จาก $mid=low+\left({\frac {\left(toFind-Array[low]\right)\times \left(high-low\right)}{Array[high]-Array[low]}}\right)$
4. เริ่มต้นเช็คเงื่อนไขภายในวงวนเพื่อปรับค่า $low$ หรือ $high$
   1. ถ้า $Array[mid]<toFind$ (ถ้าไม่ใช่ ข้ามไปทำข้อ 2.) ปรับค่า $low$ เป็น $low=mid+1$
   2. ถ้า $Array[mid]>toFind$ (ถ้าไม่ใช่ ข้ามไปทำข้อ 3.) ปรับค่า $high$ เป็น $high=mid-1$
   3. ได้ค้นพบตำแหน่งของค่าที่ต้องการค้นหา ในแถวลำดับนี้แล้ว ทำการคืนค่ากลับ นั้นก็คือ คืนค่า $mid$ กลับไป
5. ขั้นตอนนี้หมายถึงปรับค่า $low$ และ $high$ ไปเรื่อยๆจนหลุดจากวงวนแล้วยังไม่พบ ตำแหน่งที่ต้องการค้นหาดังกล่าว ให้ทำการตรวจเงื่อนไขว่า ถ้า $Array[low]=toFind$ (ถ้าไม่ใช่ ข้ามไปทำข้อ 6.) ถ้าใช่ หมายถึงค่า $low$ คือค่าตำแหน่งของค่าที่ต้องการค้นหานั้นเอง ทำการคืนค่ากลับ คือ คืนค่า $low$ กลับไป
6. ขั้นตอนนี้หมายถึง ไม่สามารถหาตำแหน่งของค่าที่ต้องการค้นหาได้ ทำการคืนค่า $-1$ กลับไป

รหัสเทียม

 function interpolationSearch(int[] sortedArray, int toFind){
      // กำหนดให้ฟังก์ชันนี้ มีการรับค่าพารามิเตอร์เป็น แถวลำดับที่จะทำการค้นหา และ ค่าที่ต้องการค้นหา
      // และคืนค่าเป็นตำแหน่งของแถวลำดับที่เก็บค่า ตรงกับ ค่าของ tofind  ส่วนกรณีที่หาไม่พบจะคืน -1

  int low = 0;
  int high = sortedArray.length - 1;
  int mid;

  while (sortedArray[low] <= toFind && sortedArray[high] >= toFind) {
    mid = low +
         ((toFind - sortedArray[low]) * (high - low)) /
         (sortedArray[high] - sortedArray[low]);

    if(sortedArray[mid] < toFind)
       low = mid + 1;
    else if (sortedArray[mid] > toFind)
       high = mid - 1;
    else
       return mid;
  }

  if(sortedArray[low] == toFind)
     return low;
  else
     return -1;  // กรณีที่หาไม่พบ จะคืนค่า -1
 }

ประสิทธิภาพการทำงาน

การค้นโดยการประมาณช่วง (interpolation search) ในกรณีเฉลี่ยการค้นลักษณะนี้จะมีประสิทธิภาพเท่ากับ $O\left(\log \log n\right)$ ซึ่งดีกว่าการค้นแบบทวิภาค (Binary search) ที่มีประสิทธิภาพเท่ากับ $O\left(\log n\right)$ แต่ในกรณีโชคร้ายคือข้อมูลมีการกระจายไม่สม่ำเสมอเลย เช่น (1,2,4,8,16,..) การค้นหาลักษณะนี้จะมีประสิทธิภาพแย่ที่สุด ซึ่งจะกลายเป็นแบบการค้นแบบเชิงเส้น (Linear search) มีประสิทธิภาพเท่ากับ $O\left(n\right)$ ดังนั้นการค้นโดยการประมาณช่วง (interpolation search) จะมีประสิทธิภาพดีเมื่อใช้กับข้อมูลที่ค่าของคำหลัก (key value) มีกระจายที่ค่อนข้างสม่ำเสมอ เช่น (1,3,4,5,7,9,10,…) และจะมีประสิทธิภาพดีที่สุดเมื่อใช้กับข้อมูลที่ค่าของคำหลัก (key value) มีกระจายอย่างสม่ำเสมอ (Uniformly Distributed) เช่น (1,2,4,6,8,10,..)

การนำไปประยุกต์ใช้งาน

การประยุกต์ใช้งานของขั้นตอนวิธี การค้นโดยการประมาณช่วง (Interpolation Search) ที่เราพบเห็นกันบ่อยในชีวิตประจำวัน เช่น การค้นหารายชื่อในสมุดโทรศัพท์ของโทรศัพท์มือถือ การค้นหาคำในพจนานุกรมอิเลกทรอนิกส์ หรือในพจนานุกรมออนไลน์ การค้นหารายชื่อหนังสือผ่านระบบสารสนเทศ ของร้านหนังสือ ฯลฯ โดยบางครั้งก็มีการนำไปประยุกต์ใช้งานร่วมกับขั้นตอนวิธีอื่นๆเพื่อให้มีประสิทธิภาพมากขึ้นด้วย

ศึกษาเพิ่มเติม

• การค้นแบบทวิภาค (Binary search)
• การค้นแบบเชิงเส้น (Linear search)
• ตารางแฮช (Hash table)
• Ternary search

อ้างอิง

• Weiss, Mark Allen (2006). Data structures and problem solving using Java, Pearson Addison Wesley
• Armenakis, A. C., Garey, L. E., Gupta, R. D., An adaptation of a root finding method to searching ordered disk files, BIT Numerical Mathematics, Volume 25, Number 4 / December, 1985.
• Sedgewick, Robert (1990), Algorithms in C, Addison-Wesley
• การค้นหาข้อมูล