如何在一个有序数组中查找某一元素

﹏ヽ暗。殇╰゛Y 2023-09-27 13:52 143阅读 0赞

##  ##

**目录**

思路一：遍历

思路二：二分查找

--------------------

## 思路一：遍历 ##

> 我们看到这个题目，大多数人首先想到的可能就是暴力求解了，将数组都i遍历一遍，将每个数据都与目标元素进行比较，如果不相等，就继续比较下一个元素。

#include<stdio.h>
    
    int main()
    {
        int arr[10] = {1,2,3,4,5,6,7,8,9,10};  //假设创建一个这样的数组
        int k = 7;  //假设要在数组中寻找数字7
        int i = 0;  //创建循环变量
        int flag = 0;  //创建一个变量来判断是否能找到，如果flag=1，则能找到，为0则找不到
        for(i=0;i<10;i++)  //循环进行十次
        {
            if(k == arr[i])  //进行判断
                {
                    flag = 1;
                    printf("找到了，下标是:%d\n",i);
                    break;  //跳出循环
                }
        }
        if(flag == 0)
        {
            printf("找不到\n");
        }
        return 0;
    }

## 思路二：二分查找 ##

这种遍历的方式虽然简单，但是如果要寻找的数组元素比较多，那么这个代码将会进行很多次比较，不能够有效的提升代码运行速度，那么我们要怎样才能既实现找元素的功能，又不浪费太多时间呢？还有一种方法就是：折半查找法，也叫做二分查找法。二分查找法就是先将第一个元素的下标赋给left，最后一个元素的下标赋给right，然后它两相加除以2得到一个新的数值mid，将mid作为下标，然后用mid所对应的元素来与我们要查找的这个数作比较，如果要查找的这个数大于mid所对应的元素，那么就将mid+1赋给left；如果要查找的这个数小于mid所对应的元素，就将mid-1赋给right，然后继续该操作直到找到我们需要的数，打印出该数对应的下标，下面就用代码来实现

#include<stdio.h>
    
    int main()
    {
        int arr[10] = {1,2,3,4,5,6,7,8,9,10};
        int k = 7;
        int left = 0;  //数组第一个元素的下标为0
        int len = sizeof(arr)/sizeof(arr[0]);  
    //求数组的长度，然后最后一个元素的下标就为len-1
        int right = len-1;
        int flag = 0;
        while(left<=right)  //这里用while循环简单一些
        {
            int mid = left+(right-left)/2;
    //这样写可以防止left+right的值超过int或long long的范围,
    //而且这里mid得定义在循环体的内部，如果在外部的话，
    //left和right就一直是第一个元素的下标和最后一个元素的下标
            if(arr[mid]<k)
            {
                left = mid+1;
            }
            else if(arr[mid]>k)
            {
                right = mid-1;
            }
            else
            {
                flag = 1;
                printf("找到了，下标是:\n",mid);
                break;
            }
        }
        if(flag == 0)
        {
            printf("找不到\n");
        }
        return 0;
    }

以上就是我对如何在一个有序数组中查找某一元素的看法，如果后续还有其他方法，我会继续对其补充。