C语言:写一个函数,实现一个整型有序数组的二分查找

简介: 思路:总体思路:(一)自定义函数部分: (1).参数:

思路:

总体思路:

(一)自定义函数部分:

               

(1).

参数:

int arr[] -- 数组首地址


int k -- 要在数组中找的数字


int sz -- 数组长度


           


定义左右下标;


               


(2).


使用二分查找法;


           


(二)主函数部分:


       


定义有序数组,设置要查找的值,求出数组元素个数。


           


调用自定义函数。


           


判断自定义函数的返回值,打印相应的情况。

自定义函数部分:

第一步:

(1). 形参的设置:

int arr[] -- 数组首地址

int k -- 要在数组中找的数字

int sz -- 数组长度

(2). 定义左右下标 -- left right

                   

实现代码:

#include <stdio.h>
int binary_search(int arr[], int k, int sz)//形参
{
  int left = 0; //左下标
  int right = sz - 1; //右下标
}
int main()
{
  return 0;
}


实现图片:


ca47ada73ebc40078bfb31de46ce1772.png

第二步:

使用二分查找方法

       

(1). 使用while循环

         

(2). 生成中间值下标 mid

int mid = left + (right - left) / 2;


left 是 小的一边,(right - left)是两者的差值,(right - left)/ 2 是差值的一半,


left + (right - left) / 2,即 小的一边 加上 差值的一半,


这时 两边是一样的,任意一边都是平均值(中间值)


           


(3).


如果中间值 小于 要找的值,


舍弃中间值和中间值左边的所有数,调整 左下标left :left = mid + 1。


如果中间值 大于 要找的值,


舍弃中间值和中间值右边的所有数,调整 右下标right :right = mid - 1。


如果中间值 等于 要找的值,


返回中间值下标mid。


           


(4). 找不到则返回 -1 。

实现代码:

int binary_search(int arr[], int k, int sz)//形参
{
  int left = 0; //左下标
  int right = sz - 1; //右下标
  //使用while循环
  while (left <= right)
  {
    //生成中间值下标 mid :
    int mid = left + (right - left) / 2;
    //二分查找:
    if (arr[mid] < k)//中间值 小于 要找的值
    {
      left = mid + 1;
      //舍弃中间值和中间值左边的所有数,
      //调整 左下标left :left = mid + 1。
    }
    else if (arr[mid] > k)//中间值 大于 要找的值
    {
      right = mid - 1;
      //舍弃中间值和中间值右边的所有数,
      //调整 右下标right :right = mid - 1。
    }
    else if (arr[mid] == k)//中间值 等于 要找的值
    {
      return mid;
      //返回中间值下标mid。
    }
  } 
  if (left > right)
  {
    return -1; //找不到则返回-1
  }
}

实现图片:


632735d2c9734c3ba3688f5a9ba34059.png

主函数部分:

(1). 定义有序数组,设置要查找的值,求出数组元素个数

             

(2). 调用自定义函数

3). 判断自定义函数返回值打印相应的情况

                   

实现代码:

#include <stdio.h>
int binary_search(int arr[], int k, int sz)//形参
{
  int left = 0; //左下标
  int right = sz - 1; //右下标
  //使用while循环
  while (left <= right)
  {
    //生成中间值下标 mid :
    int mid = left + (right - left) / 2;
    //二分查找:
    if (arr[mid] < k)//中间值 小于 要找的值
    {
      left = mid + 1;
      //舍弃中间值和中间值左边的所有数,
      //调整 左下标left :left = mid + 1。
    }
    else if (arr[mid] > k)//中间值 大于 要找的值
    {
      right = mid - 1;
      //舍弃中间值和中间值右边的所有数,
      //调整 右下标right :right = mid - 1。
    }
    else if (arr[mid] == k)//中间值 等于 要找的值
    {
      return mid;
      //返回中间值下标mid。
    }
  } 
  if (left > right)
  {
    return -1; //找不到则返回-1
  }
}
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 ret = binary_search(arr, k, sz); //ret接收返回的下标
  //判断自定义函数的返回值,打印相应的情况:
  if (ret == -1) //未找到,返回-1
  {
    printf("找不到\n");
  }
  else
  {
    printf("找到了,下标是:%d\n", ret);
  }
  return 0;
}

实现图片:

image.png

最终代码和实现效果

最终代码:

#include <stdio.h>
int binary_search(int arr[], int k, int sz)//形参
{
  int left = 0; //左下标
  int right = sz - 1; //右下标
  //使用while循环
  while (left <= right)
  {
    //生成中间值下标 mid :
    int mid = left + (right - left) / 2;
    //二分查找:
    if (arr[mid] < k)//中间值 小于 要找的值
    {
      left = mid + 1;
      //舍弃中间值和中间值左边的所有数,
      //调整 左下标left :left = mid + 1。
    }
    else if (arr[mid] > k)//中间值 大于 要找的值
    {
      right = mid - 1;
      //舍弃中间值和中间值右边的所有数,
      //调整 右下标right :right = mid - 1。
    }
    else if (arr[mid] == k)//中间值 等于 要找的值
    {
      return mid;
      //返回中间值下标mid。
    }
  } 
  if (left > right)
  {
    return -1; //找不到则返回-1
  }
}
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 ret = binary_search(arr, k, sz); //ret接收返回的下标
  //判断自定义函数的返回值,打印相应的情况:
  if (ret == -1) //未找到,返回-1
  {
    printf("找不到\n");
  }
  else
  {
    printf("找到了,下标是:%d\n", ret);
  }
  return 0;
}

实现效果:

497f92bf06d044298e2f7feeb0614560.png

相关文章
|
22天前
|
C语言 C++
C语言 之 内存函数
C语言 之 内存函数
30 3
|
13天前
|
存储 缓存 C语言
【c语言】简单的算术操作符、输入输出函数
本文介绍了C语言中的算术操作符、赋值操作符、单目操作符以及输入输出函数 `printf` 和 `scanf` 的基本用法。算术操作符包括加、减、乘、除和求余,其中除法和求余运算有特殊规则。赋值操作符用于给变量赋值,并支持复合赋值。单目操作符包括自增自减、正负号和强制类型转换。输入输出函数 `printf` 和 `scanf` 用于格式化输入和输出,支持多种占位符和格式控制。通过示例代码详细解释了这些操作符和函数的使用方法。
30 10
|
6天前
|
存储 算法 程序员
C语言:库函数
C语言的库函数是预定义的函数,用于执行常见的编程任务,如输入输出、字符串处理、数学运算等。使用库函数可以简化编程工作,提高开发效率。C标准库提供了丰富的函数,满足各种需求。
|
12天前
|
机器学习/深度学习 C语言
【c语言】一篇文章搞懂函数递归
本文详细介绍了函数递归的概念、思想及其限制条件,并通过求阶乘、打印整数每一位和求斐波那契数等实例,展示了递归的应用。递归的核心在于将大问题分解为小问题,但需注意递归可能导致效率低下和栈溢出的问题。文章最后总结了递归的优缺点,提醒读者在实际编程中合理使用递归。
35 7
|
12天前
|
存储 编译器 程序员
【c语言】函数
本文介绍了C语言中函数的基本概念,包括库函数和自定义函数的定义、使用及示例。库函数如`printf`和`scanf`,通过包含相应的头文件即可使用。自定义函数需指定返回类型、函数名、形式参数等。文中还探讨了函数的调用、形参与实参的区别、return语句的用法、函数嵌套调用、链式访问以及static关键字对变量和函数的影响,强调了static如何改变变量的生命周期和作用域,以及函数的可见性。
24 4
|
17天前
|
存储 编译器 C语言
C语言函数的定义与函数的声明的区别
C语言中,函数的定义包含函数的实现,即具体执行的代码块;而函数的声明仅描述函数的名称、返回类型和参数列表,用于告知编译器函数的存在,但不包含实现细节。声明通常放在头文件中,定义则在源文件中。
|
9天前
|
存储 C语言
【c语言】字符串函数和内存函数
本文介绍了C语言中常用的字符串函数和内存函数,包括`strlen`、`strcpy`、`strcat`、`strcmp`、`strstr`、`strncpy`、`strncat`、`strncmp`、`strtok`、`memcpy`、`memmove`和`memset`等函数的使用方法及模拟实现。文章详细讲解了每个函数的功能、参数、返回值,并提供了具体的代码示例,帮助读者更好地理解和掌握这些函数的应用。
12 0
|
9天前
|
C语言
【c语言】qsort函数及泛型冒泡排序的模拟实现
本文介绍了C语言中的`qsort`函数及其背后的回调函数概念。`qsort`函数用于对任意类型的数据进行排序,其核心在于通过函数指针调用用户自定义的比较函数。文章还详细讲解了如何实现一个泛型冒泡排序,包括比较函数、交换函数和排序函数的编写,并展示了完整的代码示例。最后,通过实际运行验证了排序的正确性,展示了泛型编程的优势。
11 0
|
12天前
|
算法 C语言
factorial函数c语言
C语言中实现阶乘函数提供了直接循环和递归两种思路,各有优劣。循环实现更适用于大规模数值,避免了栈溢出风险;而递归实现则在代码简洁度上占优,但需警惕深度递归带来的潜在问题。在实际开发中,根据具体需求与环境选择合适的实现方式至关重要。
11 0
|
22天前
|
存储 算法 C语言
【C语言】二分查找算法
【C语言】二分查找算法