从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);
}


目录
相关文章
|
2月前
|
存储 算法 C++
【C++数据结构——查找】二分查找(头歌实践教学平台习题)【合集】
二分查找的基本思想是:每次比较中间元素与目标元素的大小,如果中间元素等于目标元素,则查找成功;顺序表是线性表的一种存储方式,它用一组地址连续的存储单元依次存储线性表中的数据元素,使得逻辑上相邻的元素在物理存储位置上也相邻。第1次比较:查找范围R[0...10],比较元素R[5]:25。第1次比较:查找范围R[0...10],比较元素R[5]:25。第2次比较:查找范围R[0..4],比较元素R[2]:10。第3次比较:查找范围R[3...4],比较元素R[3]:15。,其中是顺序表中元素的个数。
145 68
【C++数据结构——查找】二分查找(头歌实践教学平台习题)【合集】
|
1月前
|
存储 机器学习/深度学习 算法
C 408—《数据结构》算法题基础篇—链表(下)
408考研——《数据结构》算法题基础篇之链表(下)。
86 29
|
1月前
|
存储 算法 C语言
C 408—《数据结构》算法题基础篇—链表(上)
408考研——《数据结构》算法题基础篇之链表(上)。
95 25
|
1月前
|
存储 人工智能 算法
C 408—《数据结构》算法题基础篇—数组(通俗易懂)
408考研——《数据结构》算法题基础篇之数组。(408算法题的入门)
72 23
|
2月前
|
负载均衡 算法
架构学习:7种负载均衡算法策略
四层负载均衡包括数据链路层、网络层和应用层负载均衡。数据链路层通过修改MAC地址转发帧;网络层通过改变IP地址实现数据包转发;应用层有多种策略,如轮循、权重轮循、随机、权重随机、一致性哈希、响应速度和最少连接数均衡,确保请求合理分配到服务器,提升性能与稳定性。
339 11
架构学习:7种负载均衡算法策略
|
2月前
|
搜索推荐 C语言
数据结构(C语言)之对归并排序的介绍与理解
归并排序是一种基于分治策略的排序算法,通过递归将数组不断分割为子数组,直到每个子数组仅剩一个元素,再逐步合并这些有序的子数组以得到最终的有序数组。递归版本中,每次分割区间为[left, mid]和[mid+1, right],确保每两个区间内数据有序后进行合并。非递归版本则通过逐步增加gap值(初始为1),先对单个元素排序,再逐步扩大到更大的区间进行合并,直至整个数组有序。归并排序的时间复杂度为O(n*logn),空间复杂度为O(n),且具有稳定性,适用于普通排序及大文件排序场景。
|
2月前
|
存储 算法 测试技术
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
55 2
|
9月前
|
机器学习/深度学习 算法 C语言
详细介绍递归算法在 C 语言中的应用,包括递归的基本概念、特点、实现方法以及实际应用案例
【6月更文挑战第15天】递归算法在C语言中是强大力量的体现,通过函数调用自身解决复杂问题。递归涉及基本概念如自调用、终止条件及栈空间管理。在C中实现递归需定义递归函数,分解问题并设定停止条件。阶乘和斐波那契数列是经典应用示例,展示了递归的优雅与效率。然而,递归可能导致栈溢出,需注意优化。学习递归深化了对“分而治之”策略的理解。**
180 7
|
10月前
|
搜索推荐 C语言 C++
【排序算法】C语言实现归并排序,包括递归和迭代两个版本
【排序算法】C语言实现归并排序,包括递归和迭代两个版本
144 1
|
2月前
|
存储 算法 C语言
【C语言程序设计——函数】素数判定(头歌实践教学平台习题)【合集】
本内容介绍了编写一个判断素数的子函数的任务,涵盖循环控制与跳转语句、算术运算符(%)、以及素数的概念。任务要求在主函数中输入整数并输出是否为素数的信息。相关知识包括 `for` 和 `while` 循环、`break` 和 `continue` 语句、取余运算符 `%` 的使用及素数定义、分布规律和应用场景。编程要求根据提示补充代码,测试说明提供了输入输出示例,最后给出通关代码和测试结果。 任务核心:编写判断素数的子函数并在主函数中调用,涉及循环结构和条件判断。
73 23