#include <stdio.h>

/* 线性查找：O(n)，不要求有序 */
int linearSearch(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) return i;
    }
    return -1;
}

/* 二分查找：O(log n)，要求数组有序（升序） */
int binarySearch(int arr[], int left, int right, int target) {
    while (left <= right) {
        int mid = left + (right - left) / 2;  /* 防溢出写法 */
        if (arr[mid] == target) return mid;    /* 找到了 */
        if (arr[mid] < target)
            left = mid + 1;   /* 目标在右半部分 */
        else
            right = mid - 1;  /* 目标在左半部分 */
    }
    return -1;  /* 未找到 */
}

/* 插值查找：O(log log n) 平均，要求数据分布均匀 */
int interpolationSearch(int arr[], int n, int target) {
    int low = 0, high = n - 1;
    while (low <= high && target >= arr[low] && target <= arr[high]) {
        /* 插值公式：根据值的大小比例估算位置 */
        int pos = low + ((target - arr[low]) * (high - low))
                        / (arr[high] - arr[low]);
        if (arr[pos] == target) return pos;
        if (arr[pos] < target)
            low = pos + 1;
        else
            high = pos - 1;
    }
    return -1;
}

int main() {
    int arr[] = {10, 20, 30, 40, 50, 60, 70, 80, 90};
    int n = 9;

    printf("线性查找 50: 索引 %d\n", linearSearch(arr, n, 50));      /* 输出: 4 */
    printf("二分查找 50: 索引 %d\n", binarySearch(arr, 0, n-1, 50)); /* 输出: 4 */
    printf("插值查找 50: 索引 %d\n", interpolationSearch(arr, n, 50)); /* 输出: 4 */
    return 0;
}