# ClassNotes0801

**Repository Path**: SKYBB_admin/ClassNotes0801

## Basic Information

- **Project Name**: ClassNotes0801
- **Description**: 二分查找
- **Primary Language**: Java
- **License**: GPL-2.0
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2018-08-01
- **Last Updated**: 2020-12-17

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# zb_java0801

# 课堂笔记
*算法-二分查找*
*集合及操作*

## 1 查找算法
### 1.1 异常

* 1 普通查找算法
	
	直接遍历集合进行查找，效率比较低；

* 2 二分查找算法

	算法思路：
		（1）在一个有序的序列中，进行某一个值的查找时，第一次和序列中间元素进行比较；
		（2）如果查找的值等于中间元素，则返回查找到的位置；
		（3）如果查找的值小于中间元素，则跳转到（1）在前半截序列进行再次查找；
		（4）如果查找的值大于中间元素，则跳转到（1）在后半截序列进行再次查找；
	注意：
		二分查找算法的前提条件是序列有序；  //用arrays.sort(数组)进行排序
		查找比较高，例如，在1024个元素找一个值，最多只需要10次就可以找到；
		需要使用递归算法；
		中间位置 = （low+high）/2; low:是当前查找序列的开始下标；hight是当前查找序列的结束下标；
		递归结束条件是：low>=gigh【没找到】  ； 找到返回下标
	例如：
		在序列：1,2,3,4,5,7,8,9,11中查找3：
		（1） 3和中间元素5比较；
		（2）3比中间元素小，则继续重复（1）在前半截序列 1,2,3,4 查找；
		（3）3和（2）中序列的中间元素2比较，找到，返回；
		查找6呢？

## 2 集合
### 2.1 集合概念

	集合：java将一组数据作为一个管理单元进行管理；集合中存储的都是对象类型；8种基本类型转换为8种包装类类型进行存储；
	集合常用的操作：
		存入元素、读取元素、遍历元素、查找、排序等操作；
		
	java中的集合分为两大类：
		Collection接口：
			Set接口：
			List接口：
		Map接口：
	
	集合学习从以下几个维度进行比较：
		存入集合的元素：
			是否可以重复？ 是否可以为null？ 是否有序？ 是否排序？
		解释：
			有序：集合中的元素的存入顺序和读取顺序一样；
			排序：集合中的元素在读取时会按照某种排序规则进行排序；

### 2.2 Set接口
	set集合：
		set集合是采用hash散列算法进行存储的集合；因为set集合采用hash散列存储，所有没有下标
		【原因：散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来确定唯一的输入值】	；
	总结：集合中凡是采用hash散列存储的集合都没有下标，不能通过下标来进行读取元素的值；
	
	Set集合遍历：
		foreach遍历；
		Iterator迭代器遍历；
		因为没有下标，所以不能使用普通for循环遍历；
	
* 1 HashSet实现类
	
	底层是使用Hash散列进行存储；
	
		| 是否可以重复  | 是否可以为null | 是否有序 | 是否排序 |
		|:---------:|:-----------:|:--------:|:-------:|   
		| 否	|	否	| 否	| 否	|

* 2 LinkedHashSet实现类
	
	底层是使用链表进行存储的；
	
		| 是否可以重复  | 是否可以为null | 是否有序 | 是否排序 |
		|:---------:|:-----------:|:--------:|:-------:|   
		| 否	|	否	| 是	| 否	|		
	
* 2 TreeSet实现类
	
	底层是使用树型结构【平衡二叉树】进行存储的；
	
		| 是否可以重复  | 是否可以为null | 是否有序 | 是否排序 |
		|: --- :|: --- :|: ----:|: --- :|   
		| 否	| 否 | 否	| 是	|
		

### 2.3 List接口	

	List集合是一组有序的集合元素；
	List有下标，可以通过下标访问集合的元素；get(下标)方法进行访问；
	
	List集合遍历：
		标准的for循环遍历；
		增强型的for循环遍历；
		Iterator迭代器遍历；
		
* 1 ArrayList

	底层是数组实现；
	
	| 是否可以重复  | 是否可以为null | 是否有序 | 是否排序 |
	|:---------:|:-----------:|:--------:|:-------:|   
	| 是	|	是	| 是	| 否	|	
	
* 2 LinkedList 
	
	底层是链表实现；	

	| 是否可以重复  | 是否可以为null | 是否有序 | 是否排序 |
	|:---------:|:-----------:|:--------:|:-------:|   
	| 是	|	是	| 是	| 否	|	

*ArrayList和LinkedList的异同点：*
	
	用法都相同；
	不同点是：底层实现不同；
	
	ArrayList底层是数组实现，特点读写快、增删慢；
		数组连续存储，有下标，可以快速的读写；增加和删除比较慢；
		应用场景：集合读写操作频繁时，使用ArrayList；
	LinkedList底层是链表实现，特点是读写慢，增删快；
		链表是不连续存储，遍历时需要每次都从头到尾依次遍历，所有读写慢，增删快；
		应用场景：集合增删频繁时，使用LinkedList；
		
* 3 Vector

	Vector集合是List接口实现子类中的线程安全类；

	

*总结*
	
	采用Hash存储的集合都是无序的；
	采用链表存储的集合都是有序的；
	采用二叉树型结构存储的集合都是排序的；
	带有排序规则的集合元素不能为null；
	没有排序功能的集合元素可以为null；



#### 参与贡献

1. Fork 本项目
2. 新建 Feat_xxx 分支
3. 提交代码
4. 新建 Pull Request


#### 码云特技

1. 使用 Readme\_XXX.md 来支持不同的语言，例如 Readme\_en.md, Readme\_zh.md
2. 码云官方博客 [blog.gitee.com](https://blog.gitee.com)
3. 你可以 [https://gitee.com/explore](https://gitee.com/explore) 这个地址来了解码云上的优秀开源项目
4. [GVP](https://gitee.com/gvp) 全称是码云最有价值开源项目，是码云综合评定出的优秀开源项目
5. 码云官方提供的使用手册 [http://git.mydoc.io/](http://git.mydoc.io/)
6. 码云封面人物是一档用来展示码云会员风采的栏目 [https://gitee.com/gitee-stars/](https://gitee.com/gitee-stars/)