二分查找基礎版
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: 要復制多少個元素為什么這樣設計？
這種設計的好處：
1）保持數組始終有序
2）插入操作高效（使用 System.arraycopy 是本地方法，速度很快）
3）利用了二分查找的高效性（O(log n)）
