ดูต้นฉบับสำหรับ การค้นหาโดยการประมาณช่วง

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

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

== ขั้นตอนวิธี ==

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

'''กำหนดให้'''
* <math>low</math> หมายถึง ค่าขอบล่าง
* <math>mid</math> หมายถึง ค่ากึ่งกลาง
* <math>high</math> หมายถึง ค่าขอบบน
* <math>Array[low]</math> หมายถึง ค่าของแถวลำดับ ณ ตำแหน่งขอบล่าง
* <math>Array[mid]</math> หมายถึง ค่าของแถวลำดับ ณ ตำแหน่งตามค่ากึ่งกลาง
* <math>Array[high]</math> หมายถึง ค่าของแถวลำดับ ณ ตำแหน่งขอบบน
* <math>toFind</math> หมายถึง ค่าที่ต้องการค้นหา

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

== รหัสเทียม ==

<source lang="cpp">
 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
 }

</source>

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

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

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

== ศึกษาเพิ่มเติม ==
* [[การค้นแบบทวิภาค]] ([[:en:Binary search|Binary search]])
* [[การค้นแบบเชิงเส้น]] ([[:en:Linear search|Linear search]])
* [[ตารางแฮช]] ([[:en:Hash table|Hash table]])
* [[:en:Ternary search|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
* [http://itd.htc.ac.th/st_it51/it5102/5139011002/DSA/Untitled-12.html การค้นหาข้อมูล]{{ลิงก์เสีย|date=กันยายน 2021 |bot=InternetArchiveBot |fix-attempted=yes }}

[[หมวดหมู่:ขั้นตอนวิธีการค้นหา]]