数据结构与算法—二分查询

一、二分查询的概念

二、算法思想

程序的非递归实现

int binaryFind(int* nums, int n,int key)
{
    int left = 0, right = n - 1;
    int mid = 0;
    int pos = -1;
    while (left <= right)
    {
        //mid=(right-left)/2+left;
        //mid=((right-left)>>1)+left;
        mid = (left + right) / 2;
        if (nums[mid] < key)
        {
            left = mid + 1;
        }
        else if(nums[mid]>key)
        {
            right = mid - 1;
        }
        else
        {
            pos = mid;
            break;
        }
    }
    return pos;
}

提问：为什么循环里面使用的是left<=right,而不是left<right呢？原因是left到right表示的是程序的规模，当他们两相等的时候，此时还有一个值没有被查询到。只有当他们错开的时候才全部被查询到。

程序的递归实现：

int binaryFind1(int* nums, int key,int left,int right)
{
    int pos = -1;
    if (left <= right)
    {
        int mid = (left + right) / 2;
        if (nums[mid] < key)
        {
            pos = binaryFind1(nums, key, mid + 1, right);
        }
        else if (nums[mid] > key)
        {
            pos = binaryFind1(nums, key, left, mid - 1);
        }
        else
        {
            pos = mid;
        }
    }
    return pos;
}

二叉查询的问题拓展：

如果数组里面有重复的数据，则返回最左边的数组下标

改法一（线性查询）：

int binaryFind(int* nums, int n, int key)
{
    int left = 0, right = n - 1;
    int mid = 0;
    int pos = -1;
    while (left <= right)
    {
        //mid=(right-left)/2+left;
        //mid=((right-left)>>1)+left;
        mid = (left + right) / 2;
        if (nums[mid] < key)
        {
            left = mid + 1;
        }
        else if (nums[mid] > key)
        {
            right = mid - 1;
        }
        else
        {
            while(mid>=left&&nums[mid-1]==key)
            {
                mid--;
            }
            pos = mid;
            break;
        }
    }
    return pos;
}

改法二（二分查询）：

int binaryFind(int* nums, int n, int key)
{
    int left = 0, right = n - 1;
    int mid = 0;
    int pos = -1;
    while (left <= right)
    {
        //mid=(right-left)/2+left;
        //mid=((right-left)>>1)+left;
        mid = (left + right) / 2;
        if (nums[mid] < key)
        {
            left = mid + 1;
        }
        else if (nums[mid] > key)
        {
            right = mid - 1;
        }
        else
        {
            if (mid == left || nums[mid - 1] != key)
            {
                pos = mid;
                break;
            }
            else
            {
                right = mid - 1;
            }
        }
    }
    return pos;
}