LeetCode35.搜索插入位置&&LeetCode704.二分查找

• 二分法使用心得
• • 35.搜索插入位置——解题代码
  • 704.二分查找——解题代码

二分法使用心得

下面的两道题的解法本质都是二分法，但在实际使用中有很多细节上的不同（不是题目不同带来的不同，而是对二分法使用的不同）。

第35题的二分法使用过程中，中间值的求法是mid = minn + (maxx-minn)/2;而在704题中，中间值的求法我用的是mid = (minn+maxx)/2;

二分法的主体思想特别容易把控，但是我觉得最关键是在对两个边界的处理以及循环条件的设置。

其实实际使用起来，感觉还是第一种更清晰，包括对边界值的变化都特别清晰，所以决定粉上第一种。

35.搜索插入位置——解题代码

int searchInsert(int* nums, int numsSize, int target)
{
    int minn = 0;
    int maxx = numsSize-1;
    while(minn<=maxx)
    {
        int mid = minn + (maxx-minn)/2;
        //目标值小于中间值
        if(nums[mid]>target)
        {
            maxx = mid-1;
        }
        //目标值大于中间值
        if(nums[mid]<target)
        {
            minn = mid+1;
        }
        //目标值等于中间值
        if(nums[mid]==target)
        {
            return mid;
        }
    }
    return maxx+1;
}

704.二分查找——解题代码

int search(int* nums, int numsSize, int target)
{
    int minn = 0;
    int maxx = numsSize-1;
    int mid = (minn+maxx)/2;
    //开始二分
    while((maxx-minn)>1)
    {
        if(target>nums[mid])
        {
            minn = mid;
            mid = (minn+maxx)/2;
        }
        if(target<nums[mid])
        {
            maxx = mid;
            mid = (minn+maxx)/2;
        }
        if(target==nums[mid])
        {
            return mid;
        }
    }
    //停止二分
    if((maxx-minn)<=1)
    {
        if(nums[maxx]==target)
        {
            return maxx;
        }
        else if(nums[minn]==target)
        {
            return minn;
        }
    }
    return -1;
}