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