二分答案算法(二分法的算法)

参考3.1 二分查找习题分类 | 算法吧 (suanfa8.com)

1.  436. 寻找右区间

题目中的关键字是找「大于等于」，最小的那个区间的下标，很显然需使用二分查找算法；

要使用二分查找，需要在有序的环境中进行，因此，需要对区间排序（可将这一步称之为预处理）；

题目要求返回索引，但是排序以后，索引信息丢失。因此在预处理的时候，就得把「起点」和「下标」的关系存起来。

刚刚好题目中说道：「你可以假定这些区间都不具有相同的起始点」，用「哈希表」正合适；

排序的时候，只需要对起点进行排序即可；

在二分查找的时候，传入的是区间的右端点，查找的是大于等于区间的右端点的第 1 个值，因此它的反面就是：小于一定不是解。根据这个「逐渐缩小搜索区间」的策略，编写二分查找算法；

public class Main {
    public int[] findRightInterval(int[][] intervals) {
    	int len=intervals.length;
    	if(len==0||len==1) {
    		return new int[] {-1}; 
    	}
    	HashMap map=new HashMap<>();
    	int[] start=new int[len];
    	int[] ans=new int[len];
    	for (int i = 0; i < len; i++) {
			map.put(intervals[i][0], i);
			start[i]=intervals[i][0];
		}
    	Arrays.sort(start);
    	for (int i = 0; i < len; i++) {
			int end=intervals[i][1];
			int index=Bin(start,end);
			if(index==-1) 
				ans[i]=-1;
			else
				ans[i]=map.get(start[index]);
		}
		return ans;

    }
    static int Bin(int[] num,int target) {
    	int len=num.length;
    	int left=0;int right=len-1;
    
    	while(left>1);
    		if(num[mid]=target)
    		return left;
    	else
    		return -1;
    }
	public static void main(String[] args) {
		Main test=new Main();
		int num[][]=new int[][] {{1,4}};
		int[] ans=test.findRightInterval(num);
		for (int i : ans) {
			System.out.print(i+" ");
		}
	}
}

2.1300. 转变数组后最接近目标值的数组和

 自己写的臭代码如下：

犯几个致命错误：

1.忽略了java的引用变量地址传递机制，下面这个例子可以很好地说明

2.注意循环当中如果要采用了引用变量地址传递机制  要仔细思考是否需要新建对象！！！！

public static void main(String[] args) {
		Main test = new Main();
		int[] arr = new int[] { 2, 3, 5 };
//		System.out.println(test.findBestValue(arr, 11));
		int[] sum=arr;
		for (int i : arr) 
			System.out.print(i+" ");
		System.out.println();
		sum[0]=99999999;
		for (int i : arr) 
			System.out.print(i+" ");
		
	}