二分查找的改进：插值查找

int search(int s[],int n,int key)
{
    int left,right,mid;
    left=0;
    right=n-1;
    while(left<=right)        //查找范围含含至少一个元素 
    {
        mid=left+(key-s[left])*(right-left)/(s[right]-s[left]);/*改进*/   
        if(s[mid]==key)     
            return mid;
        else if(s[mid]>key)
            right=mid-1;
        else 
            left=mid+1;
    }
    return -1;
}