C语言实现：折半查找（二分查找）

循环实现折半查找

直接查找，使用了while循环和if语句

#include <stdio.h>
#include  <stdlib.h>
int main()
{
    int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, };
    int key = 9;
    int left = 0;
    int right = sizeof(arr) / sizeof(arr[0]) - 1;//right是数组最后一个元素
    while (left <= right)//如果没有'left=right',那就会把'left=right'时所对应的元素遗漏掉
    {
        int mid = left + (right - left) / 2;//注意溢出
        /*先比较'=='，这样的话，可少判断来两次（分别是if(key > arr[mid])和if(key < arr[mid]))*/
        if (key == arr[mid])
        {
            printf("找到了，数组下标为: %d\n", mid);
            break;
        }
        else
        {
            if (key > arr[mid])
            {
                left = mid + 1;
            }
            else
            {
                right = mid - 1;//下标mid所对应的元素，已经判断过，是左闭右闭区间，所以取mid前一个就好
            }
        }
        if (left > right)
        {
            printf("找不到:\n");
        }
    }
    system("pause");
    return 0;
}

实现折半查找时，一定要注意区间的问题，看清楚给的是左闭右闭，还是左闭右开

1.溢出问题
 在求mid时，不能写为mid=(left+right)/2 而应该写为
    mid=left+(right-left)/2

2.如果没找到元素，记得返回"return -1;"而不要返回" return 0 ; "
   因为0是数组的第一个元素，如果写为 " return 0 ; "那就意味着找到了

3.先书写"if(data==mid)"
    因为这样可以少执行两次if判断（"if(data>mid)"和"if(data<mid)" ）
    程序效率高

1.给的区间是“左闭右闭”（[1,9])

调用了binary_search（）函数，使用了while循环和if语句。注意在函数调用时传过来的数组，只是数组首元素，而不是整个数组，所以再用sizeof 时一定要注意！

#include <stdio.h>
#include <stdlib.h>
int binary_search(int arr[], int key, int sz)
{
    int left = 0;
    int right = sz -1;
    while (left <=right)//是左闭右闭区间，需要判断left=right时的元素
    {
        int mid = left + (right - left)/2;//注意溢出
        /*先比较'=='，这样的话，可少判断来两次（分别是if(key > arr[mid])和if(key < arr[mid]))*/
        if (key == arr[mid])
        {
            return mid;
        }
        else
        {
            if (key > arr[mid])
            {
                left = mid + 1;
            }
            else
            {
                right = mid-1;//是左闭右闭区间，mid所对应的元素已经被比较过，所以去mid前一个元素就好
            }
        }
    }
    return -1;//如果找不到，记得返回'-1',不要返回'0'
}
int main()
{
    int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    int key = 7;
    int sz = sizeof(arr) / sizeof(arr[0]);
    int ret = binary_search(arr, key, sz);
    if (ret == -1)
    {
        printf("找不到\n");
    }
    else
    {
        printf("找到了,数组下标为: %d\n", ret);
    }
    system("pause");
    return 0;
}           

运行截图：

2.给的区间是左闭右开（ [1,9) )
调用了binary_search（）函数，使用了while循环和if语句。注意在函数调用时传过来的数组，只是数组首元素，而不是整个数组，所以再用sizeof 时一定要注意！

#include <stdio.h>
#include <stdlib.h>
int binary_search(int arr[], int key, int sz)
{
    int left = 0;
    int right = sz ;
    while (left <right)//是左闭右开区间，所以不需判断left=right时的元素
    {
        int mid = left + (right - left)/2;//注意溢出
        /*先比较'=='，这样的话，可少判断来两次（分别是if(key > arr[mid])和if(key < arr[mid]))*/
        if (key == arr[mid])
        {
            return mid;
        }
        else
        {
            if (key > arr[mid])
            {
                left = mid + 1;
            }
            else
            {
                right = mid;//是左闭右开区间，所以不需判断mid所对应的元素
            }
        }
    }
    return -1;//如果找不到，记得返回'-1',不要返回'0'
}
int main()
{
    int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    int key = 9;
    int sz = sizeof(arr) / sizeof(arr[0])-1;//左闭右开区间元素'9'，取不到
    int ret = binary_search(arr, key, sz);
    if (ret == -1)
    {
        printf("找不到\n");
    }
    else
    {
        printf("找到了,数组下标为: %d\n", ret);
    }
    system("pause");
    return 0;
}

运行截图：