ออเจ้าชอบความเร็วและความเสี่ยงใช่ฤๅไม่
เช่นนั้นแล้วไซร้ Interpolation search คืออัลกอฯสำหรับออเจ้า

ความเร็วระดับ O(log(log n)) มันหอมหวานเหลือเกิน แต่ก็มาพร้อมกับความเสี่ยงที่จะเกิดการ degrade เหลือเพียง O(n)

อัลกอฯนี้พัฒนามาจาก Binary Search อีกทีหนึ่ง โดยแทนที่จะซอยลงที่ละครึ่ง ๆ เราก็ทำการเดาเสียว่าหากค่ากลางมีค่าเท่านี้แล้ว ค่าที่เราต้องการจะอยู่แถว ๆ ไหน (แน่นอนว่าต้องเรียงข้อมูล (sort) เสียก่อน)

จริง ๆ โค้ดมันแทบจะเป็น Binary Search เลย เพียงแต่เราเปลี่ยนหลักการหาตัวตรงกลางให้เป็นไปตามนี้  แทนที่จะหาร 2 ง่าย ๆ เราจะทำการหาว่าคีย์ของเราเป็นกี่ % ของผลต่างของขอบช่วงค้นหา แล้วนำไปคูณกับขนาดของช่วงค้นหา 

กำหนดให้

mid = low + ((key - source[low]) * (high - low)) / (source[high] - source[low]);

int interpolationSearch(vector<int> source, int key) {
    int low = 0, high = source.size()-1, mid;

    while (source[low] <= key and source[high] >= key) {
        mid = low +
	      ((key - source[low]) * (high - low)) /
              (source[high] - source[low]);

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

จากวิธีค้นหาแบบนี้แล้ว การค้นหาแบบนี้จะได้ผลที่ดีที่สุดเมื่อข้อมูลมีการกระจายตัวสม่ำเสมอ เช่น

1, 2, 4, 5, 6, 9, 12, 15

แต่จะแย่มากในการค้นหาชุดข้อมูลที่ไม่สม่ำเสมอ ซึ่งในกรณีนี้การใช้ Binary Search จะให้ผลที่ดีว่า เช่น

1, 14, 66, 67, 102, 231, 541, 1098

ฉะนั้นจงเลือกใช้ให้เหมาะกับประเภทข้อมูล ความเสี่ยงนั้นไม่ได้เกิดจากตัวอัลกอฯ
แต่เกิดจากการที่เราไม่รู้ว่าเราทำอะไรอยู่

Risk comes from not knowing what you are doing
- Warren Buffett