【数据结构】二分查找（返回插入点）5.14

二分查找基础版

package 二分查找;
public class BinarySearch { 	
public static void main(String[] args) {		// TODO Auto-generated method stub	}     public static int
binarySearchBasic(int[] a,int target) {    	 int i=0,j=a.length-1; //设置指针初值    	 
while(i<=j) { //范围有内容    		 
int m=(i+j)/2;    		 
if(target<a[m]) {    			 
j=m-1;    		 
}else if(target>a[m]) {    			 i=m+1;    		 
}else {    			 
return m;    		 
}    	 
}    	 
return -1;	} 
}

说明：
若目标在最左边，判断语句执行L次
若目标在最右边，判断语句执行2*L次
不平衡

平衡版
目的：为了减少执行次数

package 二分查找;
public class BinarySearch { 	
public static void main(String[] args) {		// TODO Auto-generated method stub	}     public static int
binarySearchBasic(int[] a,int target) {    	 int i=0,j=a.length; //设置指针初值    	 
while(1＜j-i) { //范围有内容  		 
int m=(i+j)＞＞＞2;    		 
if(target<a[m]) {    			 
j=m;    		 //边界改变  		 
}else {    			 
i＝m;    		 //若i＝m+1，当目标等于中间值时会错过}    	 
}  
if(a[m]＝＝traget)｛return i;
｝else｛ 
return -1;	｝} 
}

Java版

package 二分查找;
public class BinarySearch { 	
public static void main(String[] args) {		// TODO Auto-generated method stub	}     public static int
binarySearchBasic(int[] a,int target) {    	 int i=0,j=a.length-1; //设置指针初值    	 
while(i<=j) { //范围有内容    		 
int m=(i+j)/2;    		 
if(target<a[m]) {    			 
j=m-1;    		 
}else if(target>a[m]) {    			 i=m+1;    		 
}else {    			 
return m;    		 
}    	 
}    	 
return -（i+1）;	//返回值 -插入点-1
} 
}

源码

private static int binarySearch0(int[] a, int key) {int low = 0, high = a.length - 1;    while (low <= high) {        
int mid = (low + high) >>> 1;        
if (a[mid] < key) 
low = mid + 1;        
else if (a[mid] > key) 
high = mid - 1;        
else return mid; // 找到时返回下标    
}    
return -(low + 1); // 未找到时返回插入点编码
}

为什么这样设计？
// 编码过程
返回值 = -(插入点 + 1)
// 解码过程插入点 = -返回值 - 1

保留插入点信息
通过数学变换，你可以反向计算出插入位置：
插入点 = -(返回值 + 1)
例如 -2 → -( -2 + 1 ) = 1
避免歧义
如果直接返回 -插入点，当插入点是 0 时，返回值也是 0，这会和「找到目标且下标为0」的情况冲突。
效率优化
查找时已经计算出了插入点，直接返回可以避免二次查找。

插入元素

int[] a = {2, 5, 8};  // 已经排好序的数组
int target = 4;        // 我们要查找/插入的数字
int i = Arrays.binarySearch(a, target);
//Java中的二分查找
int insertIndex = Math.abs(i + 1);//实际插入位置
int[] b = new int[a.length + 1];  // 新数组长度比原数组大1
// 1. 复制插入点前的元素（不包含插入点）
System.arraycopy(a, 0, b, 0, insertIndex);
// 参数解释：
// a: 源数组
// 0: 从源数组的哪个位置开始复制
// b: 目标数组
// 0: 放到目标数组的哪个位置
// insertIndex: 要复制多少个元素// 2. 插入新元素
b[insertIndex] = target;// 3. 复制插入点后的元素
System.arraycopy(a, insertIndex, b, insertIndex + 1, a.length - insertIndex);
// 参数解释：
// a: 源数组
// insertIndex: 从源数组的哪个位置开始复制
// b: 目标数组
// insertIndex + 1: 放到目标数组的哪个位置（跳过插入的新元素）
// a.length - insertIndex: 要复制多少个元素