[游戏开发]插值查找python和C++实现

python版

class insert_search():

    def search_insert(self, list, item):
        low = 0
        high = len(list) - 1

        while(low <= high):
            mid = low + (high - low) * (item - list[low]) // (list[high] - list[low])
            guess = list[mid]
            if guess == item:
                return mid
            elif guess > item:
                high = mid - 1
            else:
                low = mid + 1

        return None

    def insert_search_recursive(self, list, item, low, high):
        if high >= low:
            mid = low + (high - low) * (item - list[low]) // (list[high] - list[low])
            guess = list[mid]

            if guess == item:
                return mid
            elif guess > item:
                return self.insert_search_recursive(list, item, low, mid - 1)
            else:
                return self.insert_search_recursive(list, item, mid +1, high)

        else:
            return None

if __name__ == "__main__":
    mylist = [3, 7, 10, 12, 15, 19, 22]
    IS = insert_search()
    print(IS.search_insert(mylist, 10))
    print(IS.insert_search_recursive(mylist, 15, 0, 6))

C++版

#include "iostream"
using namespace std;

void interpolation_search(int data_array[], int element, int len)
{
	int low = 0;
	int high = len;
	while (low <= high)
	{
		int mid = low + (high - low) * (element - data_array[low]) / (data_array[high] - data_array[low]);
		int guess = data_array[mid];

		if (guess == element)
		{
			cout << "Element found at " << mid << "th index" << endl;
			return ;
		}
		else if (guess > element)
		{
			high = mid - 1;
		}
		else
		{
			low = mid + 1;
		}
	}
	cout << "Element Not Fount" << endl;
	return;
}

int main()
{
	int data_array[] = { 2, 10, 23, 44, 100, 121 };
	int length = sizeof(data_array) / sizeof(int);

	interpolation_search(data_array, 121, length);
	return 0;
}