👨🎓作者简介：一位喜欢写作，计科专业的大二菜鸟
🏡个人主页：starry陆离
📚订阅专栏：『算法笔记HNUCM-OJ』
如果文章有帮到你的话记得点赞👍+收藏💗支持一下哦
『分治』二分搜索
1.分治法
分治法的基本思想：
对于一个规模为n的问题，
- 若该问题可以容易地解决（比如说规模n较小）则直接解决，
- 否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，
- 递归地解这些子问题，
- 然后将各子问题的解合并得到原问题的解。
这种算法设计策略叫做分治法。
分治法所能解决的问题一般具有以下几个特征：
1) 该问题的规模缩小到一定的程度就可以容易地解决
2) 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。
3) 利用该问题分解出的子问题的解可以合并为该问题的解；（关键）
4) 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。（性能考虑）
【如果具备了 前两条特征，而不具备第三条特征，则可以考虑贪心算法或动态规划】
【重复地解公共的子问题用动态规划较好】
分治法的精髓：
分--将问题分解为规模更小的子问题；
治--将这些规模更小的子问题逐个击破；
合--将已解决的子问题合并，最终得出“母”问题的解；
比较经典的分治法的运用：二分搜索，快速排序，归并排序，第k大（小）元素问题。。。
（这些我都会写笔记哦，同学你还不快快收藏关注，一起学习！！！）
2.分治法的复杂度分析
分治法将规模为n的问题分成a个规模为n/b的子问题去解
- 设n0=1，且adhoc解（直接可以求解）规模为1的问题耗费1个单位时
- 设将原问题分解为a个子问题以及用merge将a个子问题的解合并为原问题的解需用f(n)个单位时间
- 用T(n)表示该分治法解规模为|P|=n的问题所需的计算时间，则有
公式展开：
3.二分搜索 T(n) = O(logn)
问题提出：在一个单调有序的无重复元素的序列中arr[left,right]，我们要找某一个元素k，怎么快速的找到呢？
很显然有一种策略：
- 我们先找中位数（中间的元素）mid，
- 要找的元素
k<arr[mid]，说明元素k在mid的左边，我们就又在arr[left,mid-1]中寻找； - 如果要找的元素
k>arr[mid]，说明元素k在mid的右边，我们就又在arr[mid+1,right]中寻找； - 如果刚好
k==arr[mid]，那就是找到了。、
4.Java代码非递归实现
例题：HNUCM-OJ
importjava.util.Scanner; publicclassMain { publicstaticvoidmain(String[] args) { Scannerscanner=newScanner(System.in); intn,target,ans,mid=0; int []num; while(scanner.hasNext()) { ans=-1; n=scanner.nextInt(); num=newint[n]; for(inti=0;i<n;++i) { num[i]=scanner.nextInt(); } target=scanner.nextInt(); //二分搜索核心代码intlow=0,high=n; while(low<=high) { mid=low+(high-low)/2; //因为数组的下标是从0开始的，所以需要将找到的下标+1，才是目标元素的位置if(num[mid]==target) {ans=mid+1;break;} elseif(num[mid]<target) {low=mid+1;} else {high=mid-1;} } System.out.println(ans); } scanner.close(); } }
5.Java代码递归实现
例题：HNUCM-OJ
importjava.util.Scanner; publicclassMain { publicstaticvoidmain(String[] args) { Scannerscanner=newScanner(System.in); intn,target,ans=0; int []num; while(scanner.hasNext()) { n=scanner.nextInt(); num=newint[n]; for(inti=0;i<n;++i) { num[i]=scanner.nextInt(); } target=scanner.nextInt(); //调用二分搜索递归函数ans=BinarySearch(num,0,n,target); //因为数组的下标是从0开始的，所以需要将找到的下标+1，才是目标元素的位置ans=(ans==-1?-1:ans+1); System.out.println(ans); } scanner.close(); } //二分搜索递归函数publicstaticintBinarySearch(int []num,Integerlow,Integerhigh,inttarget) { if(low<=high) { intmid=low+(high-low)/2; if(num[mid]==target)returnmid; elseif(num[mid]>target)returnBinarySearch(num, low, mid-1, target); elsereturnBinarySearch(num, mid+1, high, target); } else { return-1; } } }
6.Java自带二分搜索方法
查API可以知道，二分查找重载了很多方法，字符型，整型，长整型，浮点型，双精度等等，而且还可以指定查找的范围
那么如何使用这个方法呢，它的返回值又是多少？
importjava.util.Arrays; publicclassBinarySearchMy { publicstaticvoidmain(String[] args) { intnum[]= {1,2,3,4,6,7,9,12,34,56,87}; intans=Arrays.binarySearch(num, 1); intans1=Arrays.binarySearch(num, 2); intans2=Arrays.binarySearch(num, 5); intans3=Arrays.binarySearch(num, 6); intans4=Arrays.binarySearch(num, 8); intans5=Arrays.binarySearch(num, 10); System.out.println("ans:"+ans); System.out.println("ans1:"+ans1); System.out.println("ans2:"+ans2); System.out.println("ans3:"+ans3); System.out.println("ans4:"+ans4); System.out.println("ans5:"+ans5); // ans:0// ans1:1// ans2:-5// ans3:4// ans4:-7// ans5:-8 } }
分析输出可知：
- 如果找到了目标元素，返回目标元素所在的位置的下标；
- 如果没有找到，则返回的是一个负数，但不并不是随便的一个负数，它也是有讲究的，返回的是该元素应该插入的位置的负数；
7.单调有序包含重复元素的序列
如果是单调有序包含重复元素的序列，那么返回的值又是多少呢？
其实如果理解了开篇的二分的原理，不难猜到返回的应该是中间的那个元素的位置下标
如下寻找序列中的2，返回的就是中间的那个2的下标；
importjava.util.Arrays; publicclassBinarySearchMy { publicstaticvoidmain(String[] args) { intnum[]= {1,2,2,2,6,6,9,9,9,9,87}; intans1=Arrays.binarySearch(num, 2); intans3=Arrays.binarySearch(num, 6); intans5=Arrays.binarySearch(num, 9); System.out.println("ans1:"+ans1); System.out.println("ans3:"+ans3); System.out.println("ans5:"+ans5); // ans1:2// ans3:5// ans5:8 } }
8.练习题
704. 二分查找 - 力扣（LeetCode） (leetcode-cn.com)
278. 第一个错误的版本 - 力扣（LeetCode） (leetcode-cn.com)
