1.二分法

前提：元素大小已排序.
时间复杂度：O(log₂n).（1个循环/递归+判断缩小搜索范围）
适用：线性表的 顺序存储 & 链式存储 .

• 传入数组/指针，要查找的数字，数组下限值（初始化为0），上限值（初始化为数组长度-1）
• 判断边界条件 ：下限值>上限值 时，退出循环/递归
• 取中位数mid
• 判断数据落在区域，对上下限值做相应处理

递归&循环

#include "iostream"
using namespace std;

//01递归法（version1.0）
int HalfFind_01(int* my_array,int* my_search, int* my_min, int* my_max)
{
    if(*my_min > *my_max)
    {
        return -1;
    }
    int mid = (*my_max + *my_min) / 2; 
    if(*(my_array+mid)  == *my_search)
    {
        return mid;//结束递归时的边界条件
    }
    else 
    {
        if (*(my_array + mid) < *my_search)
        { 
            *my_min = mid+1;//低位 中值+1
            HalfFind_01(my_array, my_search, my_min, my_max);//递归
        }
        else
        {
            *my_max = mid-1;//高位 中值-1
            HalfFind_01(my_array, my_search, my_min, my_max);//递归
        }
    }
}
//02循环法（version1.0）
int HalfFind_02(int* my_array, int* my_search, int* my_min, int* my_max)
{
    while (*my_min <= *my_max)
    {
        int mid = (*my_max + *my_min) / 2;
        if (*(my_array + mid) == *my_search)
        {
            return mid;//结束循环时的边界条件
        }
        else
        {
            if (*(my_array + mid) < *my_search)
            {
                *my_min = mid + 1;//低位 中值+1
            }
            else
            {
                *my_max = mid - 1;//高位 中值-1
            }
        }
    }
    return -1;
    
}

int main()
{
    int arr[] = {1,3,4,5,7,9,12,16,19,55,56,57};
    int *array = arr;//不能直接传递数组名arr，会退化成指针（并且为整个数组指针）而array为单个数组元素指针
    int min = 0;//数组低位
    int max = sizeof(arr)/ sizeof(*arr)-1;//数组高位 数组名48字节/数组取地址4字节&&注意边界测试条件：-1
    int search = 0;//初始化
    cin>>search;//输入要查找的值

    //函数调用:HalfFind_02() or HalfFind_01()
    int ret = HalfFind_02(array, &search, &min, &max);
    if(  ret  ==  -1)
    {
        cout<<"未查找到！错误码："<<ret<<endl;
        //system("pause");
        return 0;
    }

    cout << "查到数组下标：" << ret << endl;
    //system("pause");
    
}

2.顺序法

前提：无.
时间复杂度：O(n).（1个for循环）
适用：线性表的 顺序存储 & 链式存储 .

• 传入数组/指针，要查找的数字，上限值（初始化为数组长度）
• 逐一按顺序查找

#include "iostream"
using namespace std;

int SeqFind(int* my_array, int* my_search, int* my_max)
{
    int i;
    for (i = 0; i<*my_max; i++)
        if ( *(my_array+i) == *my_search)
            return i;
    return -1;
}

int main()
{
    int arr[] = { 1,3,4,5,7,9,12,16,19,55,56,57 };
    int *array = arr;//不能直接传递数组名arr，会退化成指针（并且为整个数组指针）而array为单个数组元素指针
    int max = sizeof(arr) / sizeof(*arr);//数组高位 数组名48字节/数组取地址4字节
    int search = 0;//初始化
    cin >> search;//输入要查找的值

    //函数调用:HalfFind_02() or HalfFind_01()
    int ret = SeqFind(array, &search, &max);
    if (ret == -1)
    {
        cout << "未查找到！错误码：" << ret << endl;
        //system("pause");
        return 0;
    }

    cout << "查到数组下标：" << ret << endl;
    //system("pause");

}