在不重復(fù)升序數(shù)組查找目標(biāo)值
解法1
public static int binarySearchV1(int[] nums, int target) {
if (nums.length == 0) {
return -1;
}
// 遍歷區(qū)間: [left,right]
int left = 0;
int right = nums.length - 1; // 注意
// 終止條件 left == right + 1
while (left <= right) {
// 相比(left+right)/2可以避免整型溢出
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
}
}
return -1;
}
說明：
① right的初始值為nums.length-1，表示此次二分查找的區(qū)間為[left,right]瞳秽，為左閉右閉區(qū)間
②根據(jù)①雙閉區(qū)間的特性，while(left <= right)模软，滿足進入循環(huán)體條件 left <= right ，此時終止循環(huán)的條件為 left = right + 1疗我，區(qū)間為[right+1,right]為空區(qū)間，不存在未遍歷元素
③循環(huán)體內(nèi)對left和right的重新賦值南捂，left=mid+1表達式對應(yīng)新的區(qū)間為[mid+1,right]; right = mid-1表達式對應(yīng)新的區(qū)間[left,mid-1]吴裤，兩個區(qū)間都不包含nums[mid]元素，因為這個元素已經(jīng)在if (nums[mid] == target)判斷分支處理過
解法2
public static int binarySearchV2(int[] nums, int target) {
if (nums.length == 0) {
return -1;
}
// 二分查找遍歷區(qū)間: [left,right]
int left = 0;
int right = nums.length - 1; // 注意
// 終止條件為left == right
while (left < right) { // 注意和解法1的區(qū)別
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
}
}
// 注意和解法1的區(qū)別
return nums[left] == target ? left : -1;
}
說明：
本題和解法1區(qū)間同為[left,right]溺健，但是進入循環(huán)的條件卻是while(left < right)麦牺，那么終止條件為left == right，這將導(dǎo)致到最后存在區(qū)間[left,left]鞭缭，剩余一個元素未被遍歷
①對于剩下最后一個元素未被二分查找遍歷的情況剖膳，此時left=right，因此最后打補丁多判斷一次nums[left]==target
解法3
public static int binarySearchV3(int[] nums, int target) {
if (nums.length == 0) {
return -1;
}
// 二分查找遍歷區(qū)間: [left,right)
int left = 0;
int right = nums.length; // 注意
// 終止條件為left == right+1
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid; // 注意
}
}
return -1;
}
說明：
本解法采取左閉右開區(qū)間岭辣，二分查找區(qū)間 [left,right)吱晒，同時搭配進入循環(huán)條件while(left < right)，此時終止循環(huán)的條件為 left == right易结，區(qū)間為[left,left)為一個空區(qū)間
①不同于解法1和解法2枕荞，循環(huán)體內(nèi)right=mid，而不是right=mid-1搞动，這是因為查找區(qū)間左邊為開區(qū)間躏精，此時新的查找區(qū)間為[left,mid)，同樣nums[mid]不再參與下一輪二分查找
在可能重復(fù)升序數(shù)組查找目標(biāo)值左邊界
以下不再對上文已經(jīng)解釋過的內(nèi)容重新說明鹦肿，關(guān)于開閉區(qū)間與left矗烛、right的重新取值以上文為準(zhǔn)
先來看兩個初步解法
解法1
public static int leftBoundV1(int[] nums, int target) {
if (nums.length == 0) {
return -1;
}
// 二分查找遍歷區(qū)間: [left,right]
int left = 0;
int right = nums.length - 1;
// 終止條件left == right+1
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
right = mid - 1;
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
}
}
return left;
}
說明：
①不同于之前查找目標(biāo)值，查找左邊界在 if (nums[mid] == target) 符合條件時箩溃，采取進一步壓縮右邊界 right = mid-1
②為什么最后返回left瞭吃，由于循環(huán)終止條件left = right+1, 當(dāng)查找到左邊界時，一定滿足 if (nums[mid] == target)條件涣旨，此時會執(zhí)行 right = mid -1歪架，由于mid為符合條件的答案，此時mid=right+1=left
解法2
public static int leftBoundV2(int[] nums, int target) {
if (nums.length == 0) {
return -1;
}
// 二分查找遍歷區(qū)間: [left,right)
int left = 0;
int right = nums.length;
// 終止條件left == right
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
right = mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid;
}
}
return left;
}
說明：
本解法就是對解法1進行區(qū)間[left,right)的改造霹陡，因此在 if (nums[mid] == target) 符合條件時和蚪，壓縮右邊界 right = mid
①解釋為什么返回left，由于左邊界一定符合條件 if (nums[mid] == target) 烹棉，此時會執(zhí)行語句 right = mid攒霹，又因為終止循環(huán)條件為 left == right , 此時存在表達式left == mid == right，所以返回left也可以
解法1和解法2看似完美浆洗，但是沒有解決以下問題：
在數(shù)組nums={1,2,3,4,5} 里查找6催束，將返回5，很明顯nums[5]并不是6
理解這個問題前伏社，先討論下解法1和解法2left和right的取值范圍
解法1：
由于二分查找mid區(qū)間為[left,right]即[0,nums.length-1]
left初始值0抠刺，循環(huán)體內(nèi)存在表達式left=mid+1區(qū)間為[1塔淤，nums.length]，合并之后left的區(qū)間為[0,nums.length]
right初始值nums.length-1,循環(huán)體內(nèi)存在表達式right=mid-1區(qū)間為[-1矫付，nums.length-2]凯沪，合并之后right的區(qū)間為[-1,nums.length-1]解法2：
由于二分查找mid區(qū)間為[left,right)即[0,nums.length)
left初始值0，循環(huán)體內(nèi)存在表達式left=mid+1區(qū)間為[0买优，nums.length+1)妨马，合并之后left的區(qū)間為[0,nums.length+1) 即 [0,nums.length]
right初始值nums.length，循環(huán)體內(nèi)存在表達式right=mid區(qū)間為[0杀赢，nums.length)烘跺，合并之后right的區(qū)間為[0,nums.length) 即 [0,nums.length]
通過上述總結(jié)，發(fā)現(xiàn)left的區(qū)間總為[0,nums.length]脂崔，其實可以將left值理解為數(shù)組nums中有多少個元素小于target滤淳，那么在數(shù)組nums={1,2,3,4,5} 里查找6土浸，返回5的問題就很好理解了睛琳，如下圖最后返回left=1，表示有一個元素小于目標(biāo)2
那么可以對解法1進行修改（解法2修改類同默终，不贅述）
public static int leftBoundV3(int[] nums, int target) {
if (nums.length == 0) {
return -1;
}
// 二分查找遍歷區(qū)間: [left,right]
int left = 0, right = nums.length - 1;
// 終止條件: left = right + 1
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) { // 收縮右側(cè)邊界
right = mid - 1;
} else if (nums[mid] < target) {
// 搜索區(qū)間變?yōu)?[mid+1, right], nums[mid]不參與下一輪
left = mid + 1;
} else if (nums[mid] > target) {
// 搜索區(qū)間變?yōu)?[left, mid-1]汇歹，nums[mid]不參與下一輪
right = mid - 1;
}
}
if (left >= nums.length || nums[left] != target) {
return -1;
}
return left;
}
說明：
既然left取值區(qū)間為[0,nums.length]屁擅，那么新增判斷l(xiāng)eft是否超過nums.length-1
同時，由于left表示數(shù)組nums內(nèi)有多少元素小于target产弹，不代表target一定在數(shù)組內(nèi)派歌，新增判斷nums[left]!=target
在可能重復(fù)升序數(shù)組查找目標(biāo)值右邊界
和查找左邊界一樣，先來看初步解法
解法1
public static int rightBoundV1(int[] nums, int target) {
if (nums.length == 0) {
return -1;
}
// 二分查找遍歷區(qū)間: [left,right]
int left = 0, right = nums.length - 1;
// 終止條件left == right+1
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
left = mid + 1; // 注意
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
}
}
return left - 1; // 注意
}
說明：
①為什么左邊界返回left痰哨，右邊界返回left-1?
由于最后一個滿足target的右邊界滿足條件 if (nums[mid] == target) 胶果，此時執(zhí)行l(wèi)eft = mid +1，nums[target]==target斤斧，那么這個時候存在表達式left-1=mid=right早抠，因此最后返回left-1
②left、right區(qū)間撬讽？
由于mid 取值區(qū)間 [0,nums.length-1]
left初始值0蕊连，mid+1取值區(qū)間為[1,nums.length]，因此合并后left區(qū)間為[0,nums.length]
right 初始值nums.length-1锐秦，mid-1取值區(qū)間為[-1,nums.length-2]咪奖，因此合并后right區(qū)間 [-1,nums.length-1]
解法2
public static int rightBoundV2(int[] nums, int target) {
if (nums.length == 0) {
return -1;
}
// 二分查找遍歷區(qū)間: [left,right)
int left = 0, right = nums.length;
// 終止條件left == right
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
left = mid + 1; // 注意
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid;
}
}
return left - 1; // 注意
}
說明：
①為什么左邊界返回left盗忱，右邊界返回left-1?
同解法1
②left酱床、right區(qū)間？
由于mid 取值區(qū)間 [0,nums.length)
left初始值0趟佃，mid+1取值區(qū)間為[1,nums.length+1)扇谣，因此合并后left區(qū)間為[0,nums.length+1)昧捷，即[0,nums.length]
right 初始值nums.length，mid取值區(qū)間為[0,nums.length)罐寨，因此合并后right區(qū)間 [0,nums.length]
③可以看到無論是雙閉區(qū)間還是左閉右開區(qū)間靡挥，求右邊界統(tǒng)一解答都是left-1（right則由于循環(huán)結(jié)束條件不同而不同）
最后同樣需要處理一下target不在數(shù)組內(nèi)部的情況
解法3
public static int rightBoundV3(int[] nums, int target) {
if (nums.length == 0) {
return -1;
}
// 搜索區(qū)間 [left,right]
int left = 0, right = nums.length - 1;
// 終止條件 left = right+1
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
left = mid + 1;
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
}
}
if (right < 0 || nums[right] != target) { // 注意
return -1;
}
return right;
}
說明：
①和解法1一樣，本題left區(qū)間為[0,nums.length]鸯绿，right區(qū)間[-1,nums.length-1]跋破，循環(huán)終止條件left = right+1，此時解為 mid = left-1=right瓶蝴，因此需要判斷right是否小于0
②同時需要判斷nums[right] != target毒返，排除target不在數(shù)組的情況，此時的left-1或者right可以理解為有多少個元素小于等于target
