二分查找-（在一个有序数组查找某个数字n)

1.二分查找

注意前提：有序数组 ！！！！

传统方法查找的代码演示：

#include <stdio.h>

int main()
{
    //有序数组的创建
    int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
    //数组中有十个元素，相应的下标为0-9
    int k = 7; //创建要查找的元素变量
    int i = 0;
    for (i = 0; i < 10; i++)
    {
        if (arr[i] == k)
        {
            printf("找到了，下标是%d\n", i);
            break;
        }
    }
    if (i == 10)
    {
        printf("找不到\n");
    }
    return 0;
}

那么除了这个传统方法，我们还有没有别的方法呢？

思路引入：假设我今天买了一件衣服不超过300我让你猜猜多少钱？你会从数字1开始一直按照顺序猜吗？我想大部分会这样猜，你先猜200，我说猜大了，然后你又猜100，我说小了，然后你又猜150.......那这样的猜价格是不是效率更高一点呢！而这种思想这是我们二分查找法的思想。

实现原理：

代码实现：

第一步：定义left、right、mid前，我们首先要确定数组中的元素个数，上面我们写的数组中是十个元素，肉眼可见，那如果我们创建一个99个元素的数组，那我们还要一个个数数组中的元素吗？此时我们需要一个简便的方法算出数组中的元素，我们知道sizeof的作用是计算多占内存的大小，那我们可以计算出数组的内存的大小。数组所占内存=一个元素所占内存大小*元素个数。而一个元素所占大小我们也可以用sizeof计算出来。

第二步：先学会一次查找，当我们arr[mid]<k时，我们令left=mid+1以此来缩小范围，当arr[mid]>k时，我们令right=mid-1以此来缩小范围，当arr[mid]=k,查找成功：

第三步：实现循环查找，当我们left<right时说明数组中的元素我们还没有查找完，left=right时数组中只剩下一个元素查找，left>right数组中的元素全部查找完。!!!:元素找到后就break跳出循环。

完整代码呈现：

#include <stdio.h>

int main()
{
    
    int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
    int k = 7;
    int sz = sizeof(arr) / sizeof(arr[0]);
    int left = 0;
    int right = sz - 1;
    while (left <= right)
    {
        int mid = (left + right) / 2;
        if (arr[mid] < k)
        {
            left = mid + 1;
        }
        else if (arr[mid] > k)
        {
            right = mid - 1;
        }
        else
        {
            printf("找到了，下标是:%d\n", mid);
            break;
        }
    }
    if (left > right)
    {
        printf("数组中无所需要查找的元素\n");
    }
    return 0;
}

让我们运行一下试试：

下面我们换一个查找元素：查找元素是12：

以上就是我们的二分查找，大家学废了吗😜

2.花式打印hello world

二分查找学累了吧？下面我们来玩点有意思的，我们来花式打印hello world🐂

🍎：必备知识点

1.strlen函数：用来求字符串的长度的库函数，头文件是 string.h

⭐：字符串的结束标志是字符'\0',当我们将字符串存入数组：char arr[]="abc", 其实数组arr 中存入的元素有'a','b','c','\0' 。用strlen求arr数组中字符串的长 度得到的结果是3，并非4。(这个内容我在C语言基础知识梳理里面讲 过，感兴趣的可以去看一下。）

2.Sleep睡眠函数：作用是延时，程序暂停若干时间。头文件是windows.h

3.system函数：执行系统命令的函数。头文件是stdlib.h 而cls系统命令为清屏。

代码实现：

#include <stdio.h>
#include <string.h>
#include <windows.h>
#include <stdlib.h>

int main()
{
    char arr1[] = "hello world";
    char arr2[] = "###########";
    int left = 0;
    int right = strlen(arr1) - 1;

    while (left <= right)
    {
        arr2[left] = arr1[left];
        arr2[right] = arr1[right];
        printf("%s\n", arr2);
        Sleep(1000);//睡眠函数-单位是毫秒
        system("cls"); //执行系统命令的
        left++;
        right--;
    }
    return 0;
}
    
    

3.模拟登录场景

当我们登录各种软件时总是需要输入账号和密码，今天我们来模拟一下登录场景，当然实际登录 场景比我们所写的要复杂的多。

🍎：必备知识点

1：数组名本来就是地址，我们用scanf输入的时候不用用&符号。

2：比较两个字符串是否相等时我们不能用==，而应该使用strcmp这个函数。

3：strcmp函数：如果函数返回值为0，说明两个字符串相等。头文件为string.h。

模拟三次登录场景：

#include <stdio.h>
#include <string.h>

int main()
{

    int i = 0;
    char password[20] = "";

    //假设密码是：“123456”
    for (i = 0; i < 3; i++)
    {
        printf("请输入密码：");
        scanf("%s", password); //password不取地址的原因是password是数组名，数组名本来就是地址。

        if (strcmp(password, "123456") == 0) //比较2个字符串是否相等，不能使用==，应该使用strcmp函数
        {
            printf("登录成功\n");
            break;
        }
        else
        {
            printf("密码错误\n");
        }
    }
        if (i == 3)
        {
            printf("三次密码都错误，退出程序\n");
        }
        return 0;
}

4.结语

此次博客的内容就到这里，大家有什么不理解的地方或者有什么更好的见解以及文章内容有错误的地方欢迎私聊我：QQ1171327065。下篇我们更新一个小游戏，大家敬请期待！q(≧▽≦q)。看完文章觉得有收获的麻烦大家点个赞吧！😊