上代碼鳖敷，注釋里寫了具體的含義
public static int binarySearchRN(Comparable[] arr, int n, Comparable target){
//int l = 0, r = n - 1;//在數(shù)組中從[l...r]的范圍內(nèi)尋找target
//循環(huán)不變量l 與 r 就代表了需要查找的這個范圍的左右邊界，而選擇取不同的值程拭，對于這個區(qū)間來說就是開區(qū)間與閉區(qū)間的區(qū)別定踱，在修改它們的同時，也需要在循環(huán)中同步這一定義恃鞋。這也就是循環(huán)不變量的意義
//int l = 0, r = n;
//int l = -1, r = n -1;
int l = -1, r = n;//在數(shù)組中從[l...r)的范圍內(nèi)尋找target
//while (l <= r ){ //當l == r時崖媚，區(qū)間[l...r]依然有效
while (l < r) {
int mid = (l + r ) / 2;//為了防止整型溢出的問題，可以修改為l + (r - l) / 2
if(arr[mid].compareTo(target) == 0) return mid;
if(target.compareTo(arr[mid]) > 0)
// l = mid + 1; // 在[mid + 1 ... r]中尋找目標
l = mid; // 在(mid ... r)中尋找目標
else
//r = mid - 1; //在[l ... mid - 1]中尋找目標
r = mid; //在(l ... mid)中尋找目標
}
return -1;
}
//測試
public static void main(String[] args) {
int n = 1000000;
Integer[] data = MyUtil.generateOrderArray(n);
long startTime = System.currentTimeMillis();
for (int i = 0; i < n; i ++)
if(i != BinarySearch.binarySearchRN(data, data.length, i))
throw new IllegalArgumentException("error");
long endTime = System.currentTimeMillis();
System.out.println("time cost: " + (endTime - startTime) + "ms");
}
明確每一個變量的含義恤浪，就能明確循環(huán)不變量
