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

相关文章
|
2天前
|
C语言 C++
C语言变量、地址、字符及printf()/sizeof()/scanf()函数介绍
C语言变量、地址、字符及printf()/sizeof()/scanf()函数介绍
4 0
|
2天前
|
C语言
C语言数组和函数
C语言数组和函数
7 0
|
2天前
|
C语言
C语言函数及分文件编程
C语言函数及分文件编程
7 0
|
4天前
|
存储 编译器 C语言
C语言:函数
C语言:函数
21 0
|
4天前
|
机器学习/深度学习 C语言
C语言:函数递归
C语言:函数递归
|
4天前
|
存储 编译器 程序员
C语言:函数
C语言:函数
|
4天前
|
存储 C语言
C语言:字符函数和字符串函数
C语言:字符函数和字符串函数
|
4天前
|
存储 编译器 C语言
C语言:内存函数
C语言:内存函数
|
8天前
|
C语言
百度搜索:蓝易云【在C语言中关于while函数和if判断句的简单使用】
通过while函数和if判断句,可以实现循环和条件判断,使得程序可以根据不同的条件执行不同的代码块。这两个控制结构在C语言中非常重要,并在实际编程中经常被使用。买CN2云服务器,免备案服务器,高防服务器,就选蓝易云。百度搜索:蓝易云
12 4
|
18天前
|
算法 搜索推荐 程序员
C语言第二十四练 欧拉函数的利用
C语言第二十四练 欧拉函数的利用
13 0

相关产品

  • 云迁移中心