企业官网建设流程全解析

南通市建设监理协会网站,求个网站知乎,网站建设费 账务处理,线在成都网站推广公司文章目录一、什么是 Binary Search#xff08;二分查找#xff09;1.1 基本思想1.2 时间复杂度二、Java 中的 binarySearch 在哪里#xff1f;三、Arrays.binarySearch 详解#xff08;最常用#xff09;3.1 基本方法签名3.2 最简单示例四、⚠️ 使用 binarySearch 的前提…文章目录一、什么是 Binary Search二分查找1.1 基本思想1.2 时间复杂度二、Java 中的 binarySearch 在哪里三、Arrays.binarySearch 详解最常用3.1 基本方法签名3.2 最简单示例四、⚠️ 使用 binarySearch 的前提条件非常重要❗ 数组必须是“有序的”五、binarySearch 的返回值规则重点 易错5.1 找到元素5.2 没找到元素很多人不懂5.2.1 什么是插入点5.2.2 为什么不直接返回插入点5.3 通用公式六、对象数组与 Comparator 版本6.1 对象数组Comparable6.2 使用 Comparator七、Collections.binarySearchList 版本7.1 方法签名7.2 示例八、binarySearch 的源码思想简化版设计亮点九、性能与适用场景分析一、什么是 Binary Search二分查找1.1 基本思想二分查找的核心思想非常简单在一个有序序列中每次都将搜索区间缩小一半具体过程取中间元素mid比较key与mid相等 → 查找成功小于 → 去左半部分大于 → 去右半部分重复直到找到或区间为空1.2 时间复杂度时间复杂度O(log n)空间复杂度O(1)迭代实现这也是二分查找被广泛使用的原因。如果想深入了解二分查找的思想推荐看【力荐】分享丨【算法题单】二分算法二分答案/最小化最大值/最大化最小值/第K小 - 讨论 - 力扣LeetCode详细介绍了二分查找的思想干货很多在实战中慢慢掌握。二、Java 中的 binarySearch 在哪里Java 中主要有两类 binarySearch 实现类方法java.util.Arrays针对数组java.util.Collections针对List 集合三、Arrays.binarySearch 详解最常用3.1 基本方法签名publicstaticintbinarySearch(int[]a,intkey)还有大量重载版本例如binarySearch(long[]a,longkey)binarySearch(double[]a,doublekey)binarySearch(T[]a,Tkey)binarySearch(T[]a,Tkey,Comparator?superTc)binarySearch(int[]a,intfromIndex,inttoIndex,intkey)3.2 最简单示例int[]arr{1,3,5,7,9};intindexArrays.binarySearch(arr,5);System.out.println(index);// 2✔ 返回的是元素所在的下标四、⚠️ 使用 binarySearch 的前提条件非常重要❗ 数组必须是“有序的”int[]arr{5,1,9,3};Arrays.binarySearch(arr,3);// 结果是 ❌ 不确定的binarySearch 不会帮你排序如果数组无序返回结果是“未定义行为”正确用法Arrays.sort(arr);Arrays.binarySearch(arr,3);五、binarySearch 的返回值规则重点 易错5.1 找到元素返回0的整数元素索引示例int[]arr{10,20,30};Arrays.binarySearch(arr,20);// 15.2 没找到元素很多人不懂返回-(插入点)-15.2.1 什么是插入点插入点 保持数组有序时该元素应该插入的位置示例int[]arr{10,20,30,40};intrArrays.binarySearch(arr,25);System.out.println(r);// -3解释25 应该插入到 index 2返回值 -(2) - 1 -35.2.2 为什么不直接返回插入点这是一个很好的问题Java没有直接返回插入点而是采用-(插入点)-1的设计主要有以下几个重要原因①.清晰区分两种状态// 如果直接返回插入点int[]arr{1,3,5,7,9};intresult1binarySearch(arr,5);// 返回2intresult2binarySearch(arr,4);// 也返回2// 问题怎么区分是找到了5还是4应该插入到2// 需要额外检查或者用特殊值标记②.避免歧义和特殊值冲突如果直接返回插入点元素找到时返回索引元素未找到时也返回索引无法区分这两种情况例如在索引0找到元素 vs 应该插入到索引0int[]arr{10,20,30};intresult1binarySearch(arr,10);// 如果直接返回0intresult2binarySearch(arr,5);// 也应该返回0// 完全无法区分③.现有设计的优势使用负值可以一目了然看到负数就知道没找到无歧义正数索引只表示找到的位置信息完整同时包含了是否找到和插入位置intindexArrays.binarySearch(arr,key);if(index0){// 肯定找到了System.out.println(找到位置index);}else{// 肯定没找到intinsertPoint-index-1;System.out.println(未找到应插入到insertPoint);}④.对比其他方案方案A返回特殊值如-1表示未找到// 问题丢失插入位置信息intindexbinarySearch(arr,key);if(index-1){// 知道没找到但不知道插哪里}方案B返回对象/PairclassSearchResult{booleanfound;intposition;// 找到的位置或插入位置}// 问题Java 8之前没有内置Pair创建对象开销大方案C通过参数返回C风格intbinarySearch(int[]arr,intkey,IntHolderinsertPoint){// 问题API复杂需要额外参数}⑤.数学上的优雅性-(插入点)-1的设计很巧妙所有插入点 ≥ 0所以-(插入点)-1 ≤ -1因此任何index ≥ 0都只能是找到的情况转换公式简单可逆⑥.实际应用场景这种设计特别适合维护有序集合// 在有序列表中插入元素保持有序ListIntegerlistnewArrayList(Arrays.asList(1,3,5,7,9));intkey4;intindexCollections.binarySearch(list,key);if(index0){list.add(-index-1,key);// 直接使用转换后的插入位置}// 结果是 [1, 3, 4, 5, 7, 9]⑦.与历史设计的兼容性Java的集合框架TreeSet、TreeMap等内部大量使用这种模式// TreeMap.put()内部类似这样的逻辑intcmpcompare(key,currentKey);if(cmp0){// 左子树}elseif(cmp0){// 右子树}else{// 找到替换值}5.3 通用公式if(result0){// 找到了result 是索引}else{intinsertPoint-result-1;}六、对象数组与 Comparator 版本6.1 对象数组ComparableString[]arr{apple,banana,cherry};intindexArrays.binarySearch(arr,banana);⚠️ 前提元素必须实现Comparable排序规则与查找规则一致6.2 使用 ComparatorArrays.binarySearch(arr,key,comparator)示例Arrays.sort(arr,Comparator.comparingInt(String::length));intidxArrays.binarySearch(arr,pear,Comparator.comparingInt(String::length));❗排序用的 Comparator 必须和 binarySearch 用的一致七、Collections.binarySearchList 版本7.1 方法签名publicstaticTintbinarySearch(List?extendsComparable?superTlist,Tkey)或publicstaticTintbinarySearch(List?extendsTlist,Tkey,Comparator?superTc)7.2 示例ListIntegerlistArrays.asList(1,3,5,7,9);intindexCollections.binarySearch(list,7);// 3⚠️ 对LinkedList不友好内部会转为索引访问八、binarySearch 的源码思想简化版以int[]为例伪代码intlow0;inthigha.length-1;while(lowhigh){intmid(lowhigh)1;intmidVala[mid];if(midValkey)lowmid1;elseif(midValkey)highmid-1;elsereturnmid;}return-(low1);下图为java.util.Arrays;包中的源码设计亮点 1防止整数溢出也可以使用low(high-low)/2来表示返回插入点信息方便后续逻辑九、性能与适用场景分析场景是否适合静态有序数组✅ 非常适合大规模只读数据✅频繁插入删除❌不如 TreeMap / TreeSet无序数据❌坑点避免❌ 数组没排序就 binarySearch❌ 排序规则和 Comparator 不一致❌ 误以为返回 -1 表示没找到❌ 在 LinkedList 上频繁调用