折半查找法思想

qq1242009750

折半查找法思想

例子:


代码如下:

//折半查找法
int bin_Search(int *Arr, int num)
{
        int low = 0, mid, hig = MAX - 1;

        while (low <= hig)                        //如果low大于hig时就是溢出了，也就可以判断要查找的数不在数组内
        {
                mid = (hig + low) / 2;
                if (Arr[mid] < num)
                {
                        low = mid + 1;
                }
                else if(Arr[mid] > num)
                {
                        hig = mid - 1;
                }
                
                if (Arr[mid] == num)
                {
                        return mid;
                }
        }
        
        return -1;   //查找失败!
}

递归版本:

int CSearch::recursion(int *Arr, int low, int mid, int hig, int num)
{
        if (low > hig)        //判断是否出错
        {
                return -1;
        }
        
        if (Arr[mid] == num)        //判断是否找到
        {
                return mid;
        }

        return Arr[mid] > num ? recursion(Arr, low, (low + mid - 1) / 2, mid - 1, num) : recursion(Arr, mid + 1, (mid + 1 + hig) / 2, hig, num);  //判断mid的值是否大于查找值或小于（用于传递不同的参数）
}