当前课程知识点：数据结构（Data Structures） > 4. Search > 4.2 Searching of Sorted Array > Video
返回《数据结构（Data Structures）》慕课在线视频课程列表
返回《数据结构（Data Structures）》慕课在线视频列表
在接下来的一章中
我们将学习
如何在有序的数组中
进行数据查找
如果我们要查找的数据
存放在一个数组中
那么要在这个数组中
查找某个关键字
最简单直接的方法
就是从头开始
逐个元素进行对比察看
那么对有N个元素的数组来说
平均状态下
这个查找的时间复杂度
是Θ（n）
和数组中的数据元素的个数
是线性相关的
但是我们也知道
这不是一个高效的查找方法
这个查找的过程
类似于我们平时在字典中查找单词
实际上我们并不会
一个单词一个单词地
往下顺序查找
那样需要的时间会非常的长
由于在字典中的单词
它是排好序的
所以我们在查字典的时候
往往是直接翻到某一页
然后去对比一下
我们要找的单词
和当前页的单词
然后再决定
是往前翻还是往后翻
经过不多的几次翻页
我们就可以找到目标单词
在数组中进行查找
也是同样道理
如果我们能够预先
把数组中的数据进行排序
那么我们也可以借鉴
翻辞典的方法来进行查找
我们来把这个查找问题
梳理一下
我们查找问题的输入
是一个数组Array
数组中的数据
已经预先排好序了
我们把在数组中的查找的数据的范围
定为从l到r
初始化的时候
l是=0的
r是=n-1
我们在全体数据中进行查找
在这个例子中
我们要查找的关键字k是等于45
那么类似于翻字典的过程
我们是直接把查找的关键字
和数组中中间的
某个位置的数据进行对比
为了方便
我们这里选择的是
正中间的位置
我们用mid来去记录这个位置
然后我们要将这个位置的关键字
和k进行比较
如果和k相等
那么就查找成功
直接返回true
如果k是比中间位置的关键字要小
那么我们要查找的关键字k
就只能存在于mid位置的左侧
所以我们可以调整一下
查找的范围
将查找的右边界r设置为mid-1
另外一种情况就是
如果k是比中间位置的关键字大的
那么说明我们要查找的关键字k
只能存在于mid位置的右侧
所以我们可以调整一下查找的范围
将搜索的左边界l设置为mid+1
所以经过这次比较
我们的搜索范围
将会缩减为原来的一半
但这个过程还需要继续下去
所以我们这里加了一个循环语句
只要左边界l小于等于右边界
就要一直执行下去
这个查找的过程中
有两种退出的可能
一种是在第四行的语句处退出
也就是成功的找到了k
返回true
另外一种可能
就是在第十行的语句处退出
这种情况就是找遍了整个数组
都未能够找到这个k
对应的是失败的查找
这个查找过程
由于每比较一次
这个范围就会从原来缩减为一半
所以这个查找过程
我们有一个名词
称之为折半查找
英文叫Binary search
我们现在来分析一下
折半查找的时间效率
我们用T（n）来去表示
在长度为n的数组中进行折半查找
它所需要消耗的总的时间
我们知道整个查找的过程中
首先会和中间位置的元素进行比较
我们假设这个比较所需要消耗的时间
是常数C
在比较完成之后
将会在原来的一半范围内
来进行数据的查找
这个查找所消耗的时间
将会是T（n/2）
所以我们就可以得到一条递推的公式
总时间T（n）
它是等于C+T（n/2）
在极端的情况下
如果这个数组中
只有一个元素
那么查找只需要一次比较就可以完成
所以消耗的时间是常数C
综合以上的公式1和2
我们就可以推导出
T（n）=⊙（logn）
消耗的时间
是和n的对数有关系
这和顺序查找相比要高效地多
所以在有序的数组中
进行折半查找
是一种更好的选择
好的 这节课我们就讲到这里
-1. Introduction--1.1 Introduction of Data
-1.1 Introduction of Data Structure
--Introduction of Data Structure
-1.2 Data Structure and A
-1.2 Data Structure and Algorithm
--Video
-1.3 Asymptotic Analysis
-1.3 Asymptotic Analysis
--Video
-1.4 Simplifying Rules of
-1.4 Simplifying Rules of Asymptotic Analysis
--Video
-2.1 Introduction of List
-2.1 Introduction of List
--Video
-2.2 Array based List
-2.2 Array based List
--Video
-2.3 Insertion Operation on Array
-2.3 Insertion Operation on Array based List
--Video
-2.4 Remove Operation on Array based List
-2.4 Remove Operation on Array based List
--Video
-2.5 Linked list
-2.5 Linked list
--Video
-2.6 Insertion Operation on Linked list
-2.6 Insertion Operation on Linked list
--Video
-2.7 Remove Operation on Linked list
-2.7 Remove Operation on Linked list
--Video
-2.8 SetPos Operation on Linked list
-2.8 SetPos Operation on Linked list
--Video
-2.9 Stack
-2.9 Stack
--Video
-2.10 Application of Stack
--Video
-2.11 Queue
-2.11 Queue
--Video
-3.1 Definition of Binary Tree
-3.1 Definition of Binary Tree
--Video
-3.2 Implementation of Binary Tree
-3.2 Implementation of Binary Tree
--Video
-3.3Traversal
-3.3 Traversal
--Video
-3.4 Binary Search Tree
-3.4 Binary Search Tree
--Video
-3.5 Search on BST
-3.5 Search on BST
--Video
-3.6 Insertion on BST
-3.6 Insertion on BST
--Video
-3.7 Introduction of Heap
-3.7 Introduction of Heap
--Video
-3.8 Construction of Heap
-3.8 Construction of Heap
--Video
-3.9 Operations on Heap
--Video
-3.10 General Tree
--Video
-4.1 Definition of Searching
--Video
-4.2 Searching of Sorted Array
-4.2 Searching of Sorted Array
--Video
-4.3 Definition of Hash Table
--Video
-4.4 Collision in Hash Table
-4.4 Collision in Hash Table
--Video
-4.5 Extension of Linear Probing
--Video
-4.6 Insertion Operation of Hash Table
--Video
-4.7 Search Operation of Hash Table
-4.7 Search Operation of Hash Table
--Video
-5.1 Introduction of Index
--Video
-5.2 Linear Index
-5.2 Linear Index
--Video
-5.3 2-3 tree index
-5.3 2-3 tree index
--Video
-5.4 Implementation of 2-3 tree
-5.4 Implementation of 2-3 tree
--Video
-5.5 B-Tree
-5.5 B-Tree
--Video
-5.6 Insertion Operation on B+ Tree
--Video
-5.7 Deletion Operation on B+ Tree
--Video
-6.1 Definition of Graph
--Video
-6.2 Implementation of Graph
--Video
-6.3 Adjacency Matrix
--Video
-6.4 Adjacency List
--Video
-6.5 Graph Traversal - DFS
--Video
-6.6 Graph Traversal - BFS
--Video
-6.7 Topological Sort
--Video
-6.8 Shortest Path Problem
--Video
-6.9 Single Source Shortest Path
--Video
-6.10 Dijkstra Algorithm
--Video
-7.1 Sorting Problem
--Video
-7.2 Insertion Sort
--Video
-7.3 Selection Sort
--Video
-7.4 Bubble Sort
--Video
-7.5 Shell Sort
--Video
-7.6 Quick Sort
--Video
-7.7 Heap Sort
--Video
-7.8 Comparison
--Video
