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

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

我们首先想到的可能就是遍历的方法了,那么使用遍历怎样来实现呢?

#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;
}

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

相关文章
|
3天前
查找数组中最小的元素
【10月更文挑战第30天】查找数组中最小的元素。
16 5
|
24天前
|
Java 索引
|
3月前
|
算法
【算法】二分查找——在排序数组中查找元素的第一个和最后一个位置
【算法】二分查找——在排序数组中查找元素的第一个和最后一个位置
|
3月前
|
算法 C++
查找方式:依次查找与二分查找
查找方式:依次查找与二分查找
|
3月前
|
算法 索引
LeetCode第34题在排序数组中查找元素的第一个和最后一个位置
这篇文章介绍了LeetCode第34题"在排序数组中查找元素的第一个和最后一个位置"的解题方法,通过使用双指针法从数组两端向中间同时查找目标值,有效地找到了目标值的首次和最后一次出现的索引位置。
LeetCode第34题在排序数组中查找元素的第一个和最后一个位置
|
6月前
|
算法
leetcode-34:在排序数组中查找元素的第一个和最后一个位置
leetcode-34:在排序数组中查找元素的第一个和最后一个位置
32 0
|
6月前
|
算法 程序员 索引
【算法训练-二分查找 一】【基本二分】二分查找、在排序数组中查找元素的第一个和最后一个位置
【算法训练-二分查找 一】【基本二分】二分查找、在排序数组中查找元素的第一个和最后一个位置
56 0
|
算法
【算法专题突破】二分查找 - 在排序数组中查找元素的第一个和最后一个位置(17)
【算法专题突破】二分查找 - 在排序数组中查找元素的第一个和最后一个位置(17)
59 0
LeetCode-34 在排序数组中查找元素的第一个和最后一个位置
LeetCode-34 在排序数组中查找元素的第一个和最后一个位置
|
存储 算法
数组算法:倒置,查找,插入,删除
数组算法:倒置,查找,插入,删除
80 0