从0开始学习数据结构 C语言实现 1.前篇及二分查找算法

简介: 从0开始学习数据结构 C语言实现 1.前篇及二分查找算法

一、前篇

1、什么是数据结构?

数据结构是带有结构特性的数据元素的集合,它研究的是数据的逻辑结构和数据的物理结构以及它们之间的相互关系

2、时间复杂度与空间复杂度

大O符号是用于描述函数渐进行为的数学符号

常用函数的增长表

阶乘O(n!) > 指数阶(2^n) > 立方阶O(n^3) > 平方阶O(n^2) > 线性对数阶O(nlog2n) > 线性阶O(n) > 对数阶O(log2n) > 常数阶O(1)

从立方阶开始,时间复杂度较大

二、二分查找

在有序数组中查找一个值,如果找到了则返回下标,如果没找到则返回-1

方法一:遍历数组进行查找

时间复杂度:O(n)

//1.遍历算法在数组中查找一个元素
//方法体
int search(int* arr, int length, int target) {
  for (int i = 0; i < length; i++) {
    if (arr[i] == target) {
      return i;
    }
  }
}

方法二:减小循环次数进行遍历查找

时间复杂度小于O(n)

因为题目里声明是有序数组,所以当数组中的值比查找的值大时,可以直接break跳出循环,减少循环次数

//2.减小循环次数进行遍历查找
//方法体
int search2(int* arr, int length, int target) {
  for (int i = 0; i < length; i++) {
    if (arr[i] == target) {
      return i;
    }
    if (arr[i] > target) {
      break;
    }
  }
  return -1;
}

方法三;二分查找

二分思想就是将一个 有序数组 不断进行平分,直到找到为止,不断平分除以二,降低时间复杂度

时间复杂度:O(og2n)

//3.二分查找
//方法体
int binarySearch(int* arr, int target, int left, int right) {
  if (left > right) {
    return -1;
  }
  int mid = (left + right) / 2;
  if (arr[mid] == target) {
    return mid;
  }
  if (arr[mid] > target) {
    mid = binarySearch(arr, target, left, mid - 1);
    return mid;
  }
  else {
    mid = binarySearch(arr, target, mid + 1, right);
    return mid;
  }
}
int search3(int* arr, int length, int target) {
  return binarySearch(arr, target, 0, length - 1);
}


目录
相关文章
|
11天前
|
存储 算法 C语言
"揭秘C语言中的王者之树——红黑树:一场数据结构与算法的华丽舞蹈,让你的程序效率飙升,直击性能巅峰!"
【8月更文挑战第20天】红黑树是自平衡二叉查找树,通过旋转和重着色保持平衡,确保高效执行插入、删除和查找操作,时间复杂度为O(log n)。本文介绍红黑树的基本属性、存储结构及其C语言实现。红黑树遵循五项基本规则以保持平衡状态。在C语言中,节点包含数据、颜色、父节点和子节点指针。文章提供了一个示例代码框架,用于创建节点、插入节点并执行必要的修复操作以维护红黑树的特性。
37 1
|
12天前
|
算法
【初阶数据结构】复杂度算法题篇
该方法基于如下的事实:当我们将数组的元素向右移动 k 次后,尾部 kmodn 个元素会移动至数组头部,其余元素向后移动 kmodn 个位置。
|
13天前
|
机器学习/深度学习 人工智能 算法
【人工智能】线性回归模型:数据结构、算法详解与人工智能应用,附代码实现
线性回归是一种预测性建模技术,它研究的是因变量(目标)和自变量(特征)之间的关系。这种关系可以表示为一个线性方程,其中因变量是自变量的线性组合。
30 2
|
16天前
|
存储 C语言
【数据结构】c语言链表的创建插入、删除、查询、元素翻倍
【数据结构】c语言链表的创建插入、删除、查询、元素翻倍
【数据结构】c语言链表的创建插入、删除、查询、元素翻倍
|
2月前
|
存储 算法 索引
算法与数据结构
算法与数据结构
30 8
|
8天前
|
机器学习/深度学习 存储 并行计算
C语言与机器学习:K-近邻算法实现
C语言与机器学习:K-近邻算法实现
21 0
|
12天前
|
算法
【初阶数据结构篇】二叉树算法题
二叉树是否对称,即左右子树是否对称.
|
12天前
|
算法 索引
【初阶数据结构篇】单链表算法题进阶
深拷贝应该正好由 n 个全新节点组成,其中每个新节点的值都设为其对应的原节点的值。
|
12天前
|
存储 算法
【初阶数据结构篇】顺序表和链表算法题
此题可以先找到中间节点,然后把后半部分逆置,最近前后两部分一一比对,如果节点的值全部相同,则即为回文。
|
15天前
|
存储 缓存 算法
深入解析B树:数据结构、存储结构与算法优势
深入解析B树:数据结构、存储结构与算法优势

热门文章

最新文章

下一篇
云函数