【数据结构和算法】1. 数据结构和算法简介、二分搜索

本文根据 数据结构和算法入门 视频记录

1. 数据结构和算法简介

1.1 什么是数据结构？什么是算法？

什么是”数据结构和算法“？这可能是第一次接触此内容的新朋友最常有的问题。我先给大家一个比较官方的解释：

数据结构是计算机存储、组织数据的方式。
算法是一系列规定的计算步骤，为了实现特定的计算目的。

你可能更困惑了，那我换种简单的说法吧：

程序 = 数据结构 + 算法

这什么意思？我们都知道，电脑最主要功能是储存数据，计算数据，输出数据，而程序无非就是电脑中一部分数据的集合而已，所以程序也是要控制数据的。那么数据结构就是程序用来储存数据的基本单位，而算法就是为了实现特定目的，一系列操作数据的方式。简单来讲，一个程序把数据存储在特定的数据结构中，并使用特定的算法进行数据的计算。

举例来说，你要在数据库中查找一个特定的数字75，假设这个数据库用数组存储数据，并存好了100个从小打大排好序的数字，那我们可以使用两种方式来找75。第一种方式就是一个一个按顺序找，那就需要找75次才能找到我们的目标。第二种方式就是我们只找一堆数中间的那个数，如果那个数比我们要找的数小，那么我们排除此数之前的所有数，只管那个数之后的数字。如果那个数比我们要找的数大，那么我们知道我们要的数肯定排在它的前面，那就只找它之前的数。所以我们第一次会找到50，50比75小，那我们就只管50~100之间的数，然后再找中间的数75，这下就找到了，可见第二种方法比第一种方法快多了。

在这个例子中，数据库用来存储数据的数组就是数据结构，而搜索的两种方式则是特定的两种搜索算法：暴力搜索和二分搜索。如果这个数据库中数据没有排好序，那么二分查找就不适用了，我们只能使用暴力搜索。可见特定的算法需要通过特定的数据结构来实现，二分搜索基于数组这种数据结构，且其中的数字必须排好序。算法的设计需要结合数据结构和特征才行。

1.2 数据结构和算法之间的关系

但数据结构和算法不一定像数组和二分查找这个例子这样是完全分开的单独内容。数组是最简单的数据结构，而很多其他复杂的数据结构往往又集成了很多的算法在其中。

比如一个优先队列数据结构，每次你向其中加入一个新数据的时候，它都会自动帮你排序好，将优先级最高的数据放在第一个。如果我们用这个数据结构来存储数据，并设定数字大的优先级更高，那么我们每次我们想要查找最大的数字，都不需要查找，直接取优先队列第一个数字即可。可见数据结构和算法的关系密不可分，每个数据结构中往往集成了很多的算法，比如这个优先队列中就集合了某种排序算法，我们才能如此快速地拿到最大值。

这些就是数据结构和算法的基本概念：数据结构是程序储存信息的基本单位，数组就是常见的数据结构。而算法则是实现特定任务的计算步骤，比如排序算法和搜索算法的目的顾名思义就是排序和搜索。数据结构和算法之间的关系密不可分，特定算法有时候需要基于特定的数据结构，比如二分查找就要基于排好序的数组。另一方面，数据结构也往往集成了特定的算法，比如优先队列就集成了排序算法在其中。

1.3 “数据结构和算法”有那么重要吗？

很多小伙伴就问了，如今各种编程语言都有丰富的第三方代码库，不需要自己实现算法，那我们还需要学习”数据结构和算法“吗？这个问题就等价于，搬砖需不需要学习物理。如果只干搬砖砌墙的活，熟练掌握工具那就够了。但是要想设计建筑的话，还是要打好基础的。“数据结构和算法”也是计算机科学的必修课，不学也不行哈哈。

毫不夸张地说，“数据结构和算法”就是编程的内功，如果能深入掌握这方面的知识，我们就可以设计出计算效率更高的程序，比如Google这一个看起来功能单一的搜索引擎，不仅仅可以搜索相关性极高的内容，其搜索速度也是惊人的，背后的秘密就是各种搜索算法的集合。所以，好好学习”数据结构和算法“吧！

2. 二分搜索（Binary Search）

2.1 算法概念

明白基本的“数据结构和算法”的概念后，我们来具体了解下一前文例子中提到的二分搜索吧，这是个很简单的算法，但是却非常实用。

二分搜索是一种在有序数组中查找特定元素的算法。假设我们要搜索x，搜索过程从数组的中间元素开始，如果中间元素正好是x，而查找成功；否则我们利用中间位置将数组分为前、后两个子数组。如果x小于中间位置的元素，则进一步查找前一个子数组，否则进一步查找后一个子数组。重复以上步骤，直到找到满足条件的元素，或直到子数组不存在为止，代表查找不成功。

2.2 代码实现

伪代码 (Pseudocode)

search(array[], left, right, target):while(left <= right) mid = (left + right) / 2;if(array[mid] == target): return midelse if(target < array[mid]):right = mid - 1else if(target > array[mid]):left = mid + 1return -1;

Java 迭代方式（非递归方式）

public int binarySearch(int array[], int target) {int left = 0;int right = array.length - 1;while(left <= right) {  int mid = left + (right - left) / 2;if (array[mid] == target) { return mid;} else if (target < array[mid]) {right = mid - 1;} else {left = mid + 1;}}return -1;
}

Java 递归方式

public int search(int nums[], int start, int end, int target) {if(end >= start) {int mid = start + (end - start) / 2;if(nums[mid] == target) {return mid;} else if (target < nums[mid]) {return search(nums, start, mid - 1, target);} return search(nums, mid + 1, end, target);}return -1;
}

2.3 算法复杂度分析

关于复杂度的概念会在下一章节详细介绍，接下来简单分析一下时间空间复杂度，大家只要了解就好。

最糟糕的情况下，我们需要将数组迭代切分到只有一个元素，那么需要多少次才会切到只有一个元素呢？假设如果数组有n个元素，切分的次数为k，每次都切一半，也就是 n / (2^k) = 1，转换公式为 2^k = n，那么k就是log2N，所以时间复杂度为O(log2N)。

因为我们不需要额外的空间，所以空间复杂度为O(1)。