查找算法：顺序、二分、哈希

一、三种算法对比表算法时间复杂度空间复杂度要求稳定性顺序查找O(n)O(1)无无二分查找O(log n)O(1)数组有序无哈希查找O(1) 平均 / O(n) 最坏O(n)哈希函数无二、顺序查找代码publicintsequentialSearch(int[]arr,inttarget){for(inti0;iarr.length;i){if(arr[i]target)returni;}return-1;}面试问题Q什么时候用顺序查找数据量小、数组无序、链表结构、只查一次。Q时间复杂度最好 O(1)最坏 O(n)平均 O(n)。三、二分查找标准模板闭区间publicintbinarySearch(int[]arr,inttarget){intleft0,rightarr.length-1;while(leftright){intmidleft(right-left)/2;if(arr[mid]target)returnmid;if(arr[mid]target)leftmid1;elserightmid-1;}return-1;}查找插入位置LeetCode 35也可以不用,继续用新的变量就可以做左边界、右边界、插入位置的题目34和35题publicintsearchInsert(int[]nums,inttarget){intleft0,rightnums.length;while(leftright){intmidleft(right-left)/2;if(nums[mid]target)leftmid1;elserightmid;}returnleft;}面试问题Q二分查找的前提数组必须有序升序或降序。Qmid 为什么用left (right - left) / 2防止(left right)溢出。Q循环条件left right和left right的区别闭区间right len-1找不到返回 -1左闭右开right len常用于找插入位置Q有重复元素怎么找第一个/最后一个// 找第一个 targetwhile(leftright){intmidleft(right-left)/2;if(nums[mid]target){if(nums[mid]target)ansmid;rightmid-1;}elseleftmid1;}Q时间复杂度为什么是 O(log n)每次将搜索范围缩小一半log₂n 次就能找到。四、哈希查找Java 使用HashSetIntegersetnewHashSet();set.add(5);set.contains(5);// trueHashMapString,IntegermapnewHashMap();map.put(apple,5);map.get(apple);// 5面试问题Q哈希查找的时间复杂度平均 O(1)最坏 O(n)所有 key 哈希冲突到同一个桶。Q什么是哈希冲突怎么解决不同 key 算出相同索引。解决方法链地址法拉链法、开放地址法线性探测、二次探测。QJava 8 之后 HashMap 有什么优化链表长度超过 8 时转为红黑树查找从 O(n) 优化到 O(log n)。Q负载因子是什么默认多少元素个数 / 桶数量超过时扩容。默认 0.75兼顾时间和空间。Q哈希表扩容过程创建新数组原长度 2 倍重新计算 hash重新插入rehash。Q为什么重写equals()必须重写hashCode()保证相同对象的 hash 值相同否则 HashMap 中找不到。QHashMap 和 Hashtable 区别HashMap线程不安全允许 null key/valueHashtable线程安全synchronized不允许 nullQ为什么 HashMap 的容量是 2 的幂(n - 1) hash等价于取模位运算更快且均匀分布。五、如何选择场景推荐原因数据量小、无序顺序查找简单不用额外空间数据量大、有序二分查找O(log n)省空间数据量大、不要求顺序哈希查找O(1)最快需要范围查询二分查找哈希不支持需要排序后输出二分查找哈希无序六、LeetCode 练习题目类型难度704. 二分查找裸二分 简单35. 搜索插入位置二分边界 简单34. 在排序数组中查找元素的第一个和最后一个位置二分变种 中等1. 两数之和哈希 简单349. 两个数组的交集哈希 简单350. 两个数组的交集 II哈希 计数 简单七、一句话总结顺序暴力二分有序哈希最快但费空间。面试问「手写二分」必须会问「哈希原理」要能说出冲突与扩容。