對(duì)于二分查找筋现，我們經(jīng)常頭疼于它的邊界值問(wèn)題，是要【左閉右開(kāi)】（即[left, right) ）進(jìn)行搜索箱歧？還是【左閉右閉】（即[left,right] ）進(jìn)行搜索矾飞？對(duì)于【左閉右開(kāi)】的寫(xiě)法，在左右收斂時(shí)我們時(shí)常要考慮向左半段搜索時(shí)mid是否要-1后再賦給right呀邢，或向右半段搜索時(shí)mid是否要+1后再賦值給left的問(wèn)題洒沦，想著想著開(kāi)始懷疑人生。价淌。申眼。
相對(duì)于【左閉右開(kāi)】瞒津，【左閉右閉】的寫(xiě)法就比較統(tǒng)一，不過(guò)往左還是右括尸，mid都需要做一次+1或-1的操作巷蚪，比較方便記憶，當(dāng)然如果你寫(xiě)熟了并且理解了兩種寫(xiě)法濒翻，right的開(kāi)閉完全取決你的心情屁柏。。這里提供一個(gè)標(biāo)準(zhǔn)的【左閉右閉】的二分查找模板肴焊，認(rèn)準(zhǔn)了這個(gè)模板前联，后面我們均按這個(gè)模板來(lái)作答。
/**
* 標(biāo)準(zhǔn)二分的模板
*
* @param nums
* @param target
* @return
*/
private int search_template(int[] nums, int target) {
// 左閉右閉
int left = 0, right = nums.length - 1;
// 終止條件為left=right+1
while (left <= right) {
// 如果寫(xiě)成(left+right)>>1娶眷，可能溢出
int mid = left + ((right - left) >> 1);
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
}
}
return -1;
}
如果模板上面的模板看明白了似嗤，那么這道題就不難解答，我們分別定義一個(gè)尋找左邊界的方法leftBound和一個(gè)尋找右邊界的方法rightBound：
相對(duì)于二分查找模板届宠，這里多了三步（比如說(shuō)尋找左邊界的方法）：
1烁落、在發(fā)現(xiàn)找到一個(gè)target對(duì)象時(shí)，不返回豌注，而是繼續(xù)讓right=mid-1伤塌，也就是向左邊收斂，找左邊界轧铁；
2每聪、后面有兩個(gè)返回-1的條件，我們一起來(lái)看一下：
- left ≥ nums.length ：這一步考慮的是如果出現(xiàn)當(dāng)前數(shù)組中所有的元素都小于target元素齿风，那么在跳出循環(huán)前會(huì)最后一次進(jìn)入nums[mid] < target的分支药薯，而最后一次left=mid+1后，left會(huì)越界救斑，因此我們要考慮left越界的情況童本；
- nums[left] ≠ target：這一步考慮的是，如果數(shù)組中不存在target的情況脸候，那么此時(shí)left指向的元素便不是我們要的左邊界穷娱；
3、最后返回left运沦，即為要尋找的左邊界泵额。
右邊界同理，不再贅述携添。
public class Solution {
public int[] searchRange(int[] nums, int target) {
return new int[]{leftBound(nums, target), rightBound(nums, target)};
}
private int leftBound(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + ((right - left) >> 1);
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] == target) {
// 繼續(xù)向左邊收斂
right = mid - 1;
}
}
// 檢查是否越界嫁盲，或者不存在
if (left >= nums.length || nums[left] != target) {
return -1;
}
return left;
}
private int rightBound(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + ((right - left) >> 1);
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] == target) {
// 繼續(xù)向右邊收斂
left = mid + 1;
}
}
// 檢查是否越界，或者不存在
if (right < 0 || nums[right] != target) {
return -1;
}
return right;
}
}
