【Java 优选算法】二分算法(上)

  

  

欢迎关注个人主页：逸狼

  

---

  

创造不易，可以点点赞吗~

  

如有错误，欢迎指出~

  

---

  

---

  
  二分查找算法 特点:最恶心,细节最多,最容易写成死循环的算法
侧重点
1.算法原理:一样寻常是数组有序的环境(当数组无序的时间假如找到规律了,也可以)
2.模板总结一些标题后的多少行代码,但不要死记硬背,->要明确后影象)

• 淳厚的二分模板(简单但有范围)
  
• 查找左边界的二分模板
  
• 查找右边界的二分模板(2和3万能但细节多)
  

二分查找

标题链接

解法

• 解法一:暴力解法,将数组中每一个值与target比力,没有用到数组有序的特性
  
• 解法二:二分查找算法,条件是:要查找的数组有"二段性"(当发现一个规律,在某个点(可以找1/2或1/3点等等)分别,可以舍去一边,留下另一边)
  

画图举例

代码

1. class Solution {
2.     public int search(int[] nums, int t) {
3.         int left = 0, right = nums.length - 1;
4.         while(left <= right){
5.             // int mid = (left + right) / 2;
6.             int mid = left + (right - left) / 2;//如果数据量大,防止溢出
7.             if(nums[mid] < t){
8.                 left = mid + 1;
9.             }else if(nums[mid] > t){
10.                 right = mid - 1;
11.             }else{
12.                 return mid;
13.             }
14.         }
15.         return -1;
16.     }
17. }
18. //找1/3的点
19. class Solution {
20.     public int search(int[] nums, int t) {
21.         int left = 0, right = nums.length - 1;
22.         while(left <= right){
23.             // int mid = (left + right) / 2;
24.             int mid = left + (right - left) / 3;//如果数据量大,防止溢出
25.             if(nums[mid] < t){
26.                 left = mid + 1;
27.             }else if(nums[mid] > t){
28.                 right = mid - 1;
29.             }else{
30.                 return mid;
31.             }
32.         }
33.         return -1;
34.     }
35. }

复制代码

在排序数组中查找元素的第一个和末了一个位置

标题链接

解法

解法一:暴力查找O(n),从前往后遍历,找到第一个目标值标记为begin,再找到末了一个目标值标记为last,
解法二:
查找左端点(分为两段区间,左边肯定不含目标值,右边大概含有)
        分两种环境 1. x<target , left = mid + 1 在[left, right]区间探求
                           2. x >= target, right = mid 在[left, right]区间探求
        循环条件:利用left < right, 思量三种环境:a,有用果,b,全都大于target,c,全都小于target 
        利用二段性,当left = right 的时间,就是最闭幕果,无须判定(假如判定,就会死循环)
        求中点方式:利用left + (right - left) / 2
查找右端点(分为两段区间,左边大概含有目标值,右边肯定不含)
        分两种环境 1. x <= target , left = mid  在[left, right]区间探求
                           2. x > target, right = mid - 1 在[left, right]区间探求
        循环条件:利用left < right, 思量三种环境:a,有用果,b,全都大于target,c,全都小于target 
        利用二段性,当left = right 的时间,就是最闭幕果,无须判定(假如判定,就会死循环)
        求中点方式:利用left + (right - left + 1) / 2
找中点的方法重要思量的是 遍历到末了只剩两个元素了,left第一个,right第二个

•         假如利用left + (right - left)/2的方式,mid处在第一个位置
  
•         利用left+ (right - left + 1) / 2,mid处在第二个位置
  

留意要思量空数组和判定效果是否存在 
画图举例

代码

1. class Solution {
2.     public int[] searchRange(int[] nums, int t) {
3.         int[] ret = new int[2];
4.         ret[0] = -1; ret[1] = -1;//将数组初始化
5.         //排除空数组
6.         if(nums.length == 0) return ret;
8.         //找左端点
9.         int left = 0, right = nums.length - 1;
10.         while(left < right){
11.             int midl = left + (right - left) / 2;
12.             if(nums[midl] < t){
13.                 left = midl + 1;
14.             }else{
15.                 right = midl;
16.             }
17.         }
18.         //判断是否有结果
19.         if(nums[left] != t) return ret;
20.         else ret[0] = left;
22.         //找右端点
23.         left = 0; right = nums.length - 1;
24.         while(left < right){
25.             int midr = left + (right - left + 1) / 2;
26.             if(nums[midr] <= t){
27.                 left = midr;
28.             }else{
29.                 right = midr - 1;
30.             }
31.         }
32.         if(nums[left] != t) return ret;
33.         else ret[1] = right;
34.         return ret;   
35.     }
36. }

复制代码

搜刮插入位置

标题链接

解法

分析标题得出 假如有目标值就返回下标,假如目标值不存在就插入
利用二分算法求左端点,求得的左端点nums[left]肯定是大于target,但是也有特殊环境,nums中全部的数都小于target,那么返回的的值应该是left + 1
画图举例

代码

1. class Solution {
2.     public int searchInsert(int[] nums, int target) {
3.         int left = 0, right = nums.length - 1;
4.         while(left < right){
5.             int mid = left + (right - left) / 2;
6.             if(nums[mid] < target) left = mid + 1;
7.             else right = mid;
8.         }
9.         if(nums[left] < target) return left + 1;
10.         return left;
11.     }
12. }

复制代码

x的平方根

标题链接

解法

解法一:暴力解法,从1开始盘算平方,分别与目标数x比力,找到与x相相迩来且小于即是x的值,比如x=17,要找的就是16,即4的平方
解法二: 二分查找

• 当mid * mid <= x ,left = mid
  
• 当mid * mid > x ,right = mid - 1;
  

留意区间范围包罗0~1
画图举例

代码

1. class Solution {
2.     public int mySqrt(int x) {
3.         if(x < 1) return 0;
4.         long left = 1, right = x;
5.         while(left < right){
6.             long mid = left + (right - left + 1) / 2;
7.             if(mid * mid <= x) left = mid;
8.             else right = mid - 1;
9.         }
10.         return (int)left;
11.     }
12. }

复制代码