【C语言】在有序数组中查找某个特定的值(二分查找法)

简介: 【C语言】在有序数组中查找某个特定的值(二分查找法)

遍历数组法

有序数组中查找某个特定的值,那我们就直接遍历整个数组就行了,这是最简单的一种方法

#include<stdio.h>
int main()
{
  int arr[10] = { 1,2,3,4,5,6,7,8,9,10 };
  int k = 7;
  int i = 0;
  for (i = 0; i < 10; i++)
  {
    if (7 == arr[i])
      printf("找到了是下标为%d\n", i);
  }
  return 0;
}

这样的方法确实简单,但是效率比较低。接下来我们就进入重点我们介绍二分查找法(也叫折半查找法)

二分查找法

为什么上面的那个不好呢?打个比方。假如你买了一件羽绒服,让我来猜猜你花了多少钱,我难道是从1开始猜吗?我可能会说300?350? 400?

这样才更贴近生活

int main()
{
  int arr[10] = { 1,2,3,4,5,6,7,8,9,10 };
  int num = sizeof(arr) / sizeof(arr[0]);
  int left = 0;
  int right = num - 1;
  int mid = left + right / 2;
  return 0;
}

利用sizeof的这个语句,我们能够知道数组一共有多少元素,left 是 int 类型因为我们等下要用它从当数组的下标,right 的值为num-1 也就是10 -1 =9 ,9就是最后一个元素的下标,mid 就是用两数的平均数得出。

接下来我们再接着讲解。

left 变成了mid+1也就是 arr[mid+1],但是我们要将arr[mid ]与7比较才能知道要排除那些值,那怎么办呢?

我们就应该再换一个arr[mid]来与7比较,这里也有循环的意思了。

再变化

最后一步分析

最后咱们再把arr[mid]与7比较一下,发现两者相等就行了。

总代码过程

我们看完这个过程一个就知道这是个循环,你也可以自己试一试,不会再看下面的过程,当然只供参考,每个人有其独特的想法

#define  _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
int main()
{
  int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
  int k = 7;
  int num = sizeof(arr) / sizeof(arr[0]);
  int left = 0;//左下标
  int right = num - 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;
}

这个代码要注意几个点, 第一点:就是要学会计算数组元素(利用sizeof),第二点:要注意每次与K比大小后要把mid的值改变,最后:要注意while()里的条件,这个写<=而不是< 是因为当left right mid都在一个地方时,还是需要进行一次比较,才算真正找到,不然当left与right相等时,是不会再计算mid的就是说,else的语句是不会进去的,也就不会告诉你 找到没有。

你也可以试试把K值设为3 自己再分析一遍,巩固一下。

这篇文章就到这里了,作者能力有限,如有错误请大胆指出。

最后都看到这里请点个赞把,这对我真的很重要


目录
相关文章
|
5月前
|
C语言
【C语言刷题系列】合并两个有序数组
【C语言刷题系列】合并两个有序数组
|
1月前
|
存储 算法 C语言
【C语言】二分查找算法
【C语言】二分查找算法
|
5月前
|
存储 算法 C语言
二分查找算法的概念、原理、效率以及使用C语言循环和数组的简单实现
二分查找算法的概念、原理、效率以及使用C语言循环和数组的简单实现
|
5月前
|
C语言
C语言----数组----二分查找
C语言----数组----二分查找
|
5月前
|
C语言
C语言--通过函数实现二分查找
C语言--通过函数实现二分查找
|
6月前
|
C语言 数据安全/隐私保护
【C语言】分支和循环的应用(二分查找、字符移动、模拟登录界面)
【C语言】分支和循环的应用(二分查找、字符移动、模拟登录界面)
45 0
|
6月前
|
存储 搜索推荐 C语言
Leetcode—合并两个有序数组—C语言
Leetcode—合并两个有序数组—C语言
|
6月前
|
算法 C语言
【C语言】二分查找
【C语言】二分查找
|
6月前
|
C语言
C语言——二分查找(在万千之中快速找到你)
C语言——二分查找(在万千之中快速找到你)
40 0
|
6月前
|
编译器 程序员 C语言
【C语言】变长数组,二分查找和数组之间自动替换的实现
【C语言】变长数组,二分查找和数组之间自动替换的实现