算法入门C——704 二分查找

LeetCode刷题——算法学习计划（入门部分）

• 思路介绍
• 我的第一次正确提交
• 官方版本

由于本人学算法只是为了巩固C语言基础，所以就不会去深挖算法之根本

算法：二分法查找适用于数据量较大时，但是数据需要先排好顺序。主要思想是：（设查找的数组区间为array[low, high]）
（1）确定该区间的中间位置K（2）将查找的值T与array[k]比较。若相等，查找成功返回此位置；否则确定新的查找区域，继续二分查找。区域确定如下：a.array[k]>T 由数组的有序性可知array[k,k+1,……,high]>T;故新的区间为array[low,……，K-1]b.array[k]

二分法在用编程语言（我这里用的是C）上实现起来还是有很多细节需要注意的的，感兴趣的可以去https://leetcode-cn.com/problems/binary-search/solution/看看。

虽然题目很简单，但我依然错了很多次，哪怕是最后一次成功了，也还是有很多可优化的地方

int search(int* nums, int numsSize, int target)
{
    int i = 0;
    int left = 0;
    int right = numsSize - 1;
    int mid = (right + left) / 2;
    if(nums[mid] == target)
        return mid;     
    if(target < nums[0] || target > nums[numsSize - 1])
        return -1;
    while(left != right) //这是最大的可优化之处，改成<=，就可以去掉while上面两个if
    {         
        if(nums[mid] > target)
            right = mid - 1;
        else if(nums[mid] < target)
            left = mid + 1;
        mid = (right + left) / 2; 
        if(nums[mid] == target)
            return mid;     
    }
    return -1;
}

下面是官方版本，也可能是网友的版本（大众版本）

mid = (right - left) / 2 + left; 可以防止left+right溢出（超出整数的范围）

int search(int* nums, int numsSize, int target)
{
    int i = 0;
    int left = 0;
     int mid = 0;
    int right = numsSize - 1;     
    while(left <= right)
    {      
        mid = (right - left) / 2 + left;  
        if(nums[mid] == target)
            return mid;      
        else if(nums[mid] > target)
            right = mid - 1;
        else 
            left = mid + 1;
    }
    return -1;
}

下面是我的几个失败的提交记录

1. 没考虑好while的结束条件，特别是left = mid和right=mid
   

int search(int* nums, int numsSize, int target)
{
    int i = 0;
    int left = 0;
    int right = numsSize - 1;
    int mid = 0;
    while(right != left)
    {
        mid = (right + left) / 2;
        if(nums[mid] == target)
            return mid;
        else if(nums[mid] > target)
            right = mid;
        else if(nums[mid] < target)
            left = mid;
    }
    return -1;
}

2. 没考虑单个元素的数组
   

int search(int* nums, int numsSize, int target)
{
    int i = 0;
    int left = 0;
    int right = numsSize - 1;
    int mid = (right + left) / 2; 
    while(left != right)
    {         
        if(nums[mid] > target)
            right = mid - 1;
        else if(nums[mid] < target)
            left = mid + 1;
        mid = (right + left) / 2; 
        if(nums[mid] == target)
            return mid;     
    }
    return -1;
}

3. 没考虑小于数组最小值和大于数组最大值的数字
   

int search(int* nums, int numsSize, int target)
{
    int i = 0;
    int left = 0;
    int right = numsSize - 1;
    int mid = (right + left) / 2;
    if(nums[mid] == target)
        return mid;     
    while(left != right)
    {         
        if(nums[mid] > target)
            right = mid - 1;
        else if(nums[mid] < target)
            left = mid + 1;
        mid = (right + left) / 2; 
        if(nums[mid] == target)
            return mid;     
    }
    return -1;
}