我记得有个 插值查找 跟 二分查找有点像，是二分的变形。

我只是知道有这个东西

这是个插入法排序，但我没看懂，谁看懂的话麻烦给讲下
#include<stdio.h>
void main()
{
    int a[10]={191,3,6,4,11,7,25,13,89,10},i,j,k;
    for(i=1;i<10;i++)
    {
        k=a[i];
        j=i-1;
        while(j>=0&&k>a[j])
        {
            a[j+1]=a[j];
            j--;
        }
        a[j+1]=k;
    }
    for(i=0;i<10;i++)
        printf("%d ",a[i]);
    printf("\n");
}

就是拿出一个数字 看他前面的比他大比他小
要是排升序的话 就尽量把比他大的往后移
降序就是把比他小的往后移
否则不动

[ 本帖最后由 a351357741 于 2010-9-17 21:32 编辑 ]

明白了。。我一直已认定他是要拍升序的，所以咋都看不懂。。。

你的附件中讲的很好了！为什么还要在这里由此一问呢？？
比如：

[问题描述]
给定一个由n个不同的数组成的集合S，求其中第i小的元素。
[分析]
相信大家对这个问题都很熟悉，让我们回顾一下二分查找是如何应用于该问题上的。
（1）    确定待查找元素在S中
（2）    在n个元素中随机取出一个记为x，将x作基准
（3）    设S中比元素x小的有p个。
如果i<p，表示我们所要寻找的元素比x小，我们就将范围确定为S中比x小的元素，求该范围内第i个元素；
如果i>p，表示我们所要寻找的元素比x大，我们就将范围确定为S中比x大的元素，求该范围内第i-p-1个元素；
如果i=p，表示第i小的元素就是x。
（4）    如果找出x，输出；否则转至（2）
因为x是随机选出的，由简单的概率分析，可得算法的复杂度期望值为O(n)。
[小结]
举这个例子，是想提醒大家两点：
第一，不要想当然认为二分查找就一定与logn有关。算法中的第（3）步，即我们通常所说的“分”并不要求每一次都必须在O(1)时间进行，“分”可以是建立在对序列的有效处理之上（比如上面这个例子中使用了类似于快速排序中的集合分割）。
第二，二分算法的“分”并不要求每次都必须平均（因为有时候可能很难做到这一点），只要不是每次都不平均就已经可以产生高效的算法了，这样也给使用随机化算法带来了契机。

就是一个用二分法的变种降低时间复杂度的很好例子！

呃 感谢楼上

强帖， 学习之