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


目录
相关文章
|
20小时前
|
存储 算法 Java
【数据结构与算法】1、学习动态数组数据结构(基本模拟实现 Java 的 ArrayList 实现增删改查)
【数据结构与算法】1、学习动态数组数据结构(基本模拟实现 Java 的 ArrayList 实现增删改查)
5 0
|
21小时前
|
算法 程序员 数据处理
算法与人生 揭秘C语言中高效搜索的秘诀——二分查找算法详解
算法与人生 揭秘C语言中高效搜索的秘诀——二分查找算法详解
|
22小时前
|
算法
【数据结构】复杂度学习
【数据结构】复杂度学习
|
3天前
|
存储 缓存 算法
【数据结构查找算法篇】----散列查找【实战项目】
【数据结构查找算法篇】----散列查找【实战项目】
22 10
|
3天前
|
机器学习/深度学习 算法 Java
【数据结构查找算法篇】----二分查找【实战项目】
【数据结构查找算法篇】----二分查找【实战项目】
7 1
|
3天前
|
存储 算法 Java
【数据结构查找算法篇】----线性查找【实战项目】
【数据结构查找算法篇】----线性查找【实战项目】
13 5
|
3天前
|
存储 分布式计算 搜索推荐
【数据结构排序算法篇】----对十大经典算法的总结
【数据结构排序算法篇】----对十大经典算法的总结
8 0
|
3天前
|
存储 搜索推荐 Java
【数据结构排序算法篇】----桶排序【实战演练】
【数据结构排序算法篇】----桶排序【实战演练】
25 5
|
3天前
|
搜索推荐 算法 Java
【数据结构排序算法篇】----基数排序【实战演练】
【数据结构排序算法篇】----基数排序【实战演练】
19 3
|
3天前
|
搜索推荐 算法 Java
【数据结构排序算法篇】----希尔排序【实战演练】
【数据结构排序算法篇】----希尔排序【实战演练】
10 2

相关产品

  • 云迁移中心