今日主題每窖，二分查找。
- 計算mid的時候需要防止溢出誊辉，當left和right太大時，
mid = ( left + right ) / 2有可能會移除亡脑，因此堕澄，最好使用mid = left + ( right - left ) / 2邀跃。
704. 二分查找
問題描述
給定一個 n 個元素有序的（升序）整型數(shù)組 nums 和一個目標值 target ，寫一個函數(shù)搜索 nums 中的 target蛙紫，如果目標值存在返回下標拍屑，否則返回 -1。
解題思路
采用兩端都閉合的搜索區(qū)間[left坑傅，right]實現(xiàn)僵驰。
代碼實現(xiàn)
class Solution {
public int search(int[] nums, int target) {
int index = -1;
int left = 0, right = nums.length - 1;
while(left <= right){
int mid = left + (right -left) / 2;
if(nums[mid] > target){
//target在mid左側,搜索區(qū)間變?yōu)閇left, mid - 1]
right = mid - 1;
}else if(nums[mid] < target){
//target在mid右側,搜索區(qū)間變?yōu)閇mid + 1, right]
left = mid + 1;
}else{
//找到了target, 結束循環(huán)
index = mid;
break;
}
}
return index;
}
}
34. 在排序數(shù)組中查找元素的第一個和最后一個位置
問題描述
給定一個按照升序排列的整數(shù)數(shù)組 nums，和一個目標值 target唁毒。找出給定目標值在數(shù)組中的開始位置和結束位置蒜茴。
如果數(shù)組中不存在目標值 target，返回 [-1, -1]枉证。
解題思路
用兩次二分查找矮男，分別找到target在數(shù)組中的左右邊界即可。
代碼實現(xiàn)
class Solution {
public int[] searchRange(int[] nums, int target) {
int len = nums.length;
int[] res = new int[] {-1, -1};
if(len > 0){
res[0] = getLeftBound(nums,target);
res[1] = getRightBound(nums, target);
}
return res;
}
//(1)找出給定目標值在數(shù)組中的開始位置室谚，目標值不存在則返回-1
public int getLeftBound(int[] nums, int target){
int left = 0, right = nums.length - 1;
while(left <= right){
int mid = left + (right -left) / 2;
if(nums[mid] > target){
//target在mid左側,搜索區(qū)間變?yōu)閇left, mid - 1]
right = mid - 1;
}else if(nums[mid] < target){
//target在mid右側,搜索區(qū)間變?yōu)閇mid + 1, right]
left = mid + 1;
}else{
//nums[mid] == target不返回毡鉴，繼續(xù)向左搜索左邊界
right = mid - 1;
}
}
//循環(huán)結束時，left = right + 1秒赤。
if(left >= nums.length || nums[left] != target){
//如果所有元素都小于target猪瞬，則left會越界
return -1;
}
return left;
}
//(2)找出給定目標值在數(shù)組中的結束位置，目標值不存在則返回-1
public int getRightBound(int[] nums, int target){
int left = 0, right = nums.length - 1;
while(left <= right){
int mid = left + (right -left) / 2;
if(nums[mid] > target){
//target在mid左側,搜索區(qū)間變?yōu)閇left, mid - 1]
right = mid - 1;
}else if(nums[mid] < target){
//target在mid右側,搜索區(qū)間變?yōu)閇mid + 1, right]
left = mid + 1;
}else{
//nums[mid] == target不返回入篮，繼續(xù)向右搜索右邊界
left = mid + 1;
}
}
//循環(huán)結束時陈瘦，right = left - 1。
if(right < 0 || nums[right] != target){
//如果所有元素都大于target潮售，則right會越界
return -1;
}
return right;
}
}
33. 搜索旋轉排序數(shù)組
問題描述
整數(shù)數(shù)組 nums 按升序排列痊项，數(shù)組中的值 互不相同 。
在傳遞給函數(shù)之前酥诽，nums 在預先未知的某個下標 k（0 <= k < nums.length）上進行了 旋轉鞍泉，使數(shù)組變?yōu)?[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下標 從 0 開始 計數(shù)）。例如肮帐， [0,1,2,4,5,6,7] 在下標 3 處經(jīng)旋轉后可能變?yōu)?[4,5,6,7,0,1,2] 咖驮。
給你 旋轉后 的數(shù)組 nums 和一個整數(shù) target ，如果 nums 中存在這個目標值 target 训枢，則返回它的索引托修，否則返回 -1 。
你能設計一個時間復雜度為 O(log n) 的解決方案嗎恒界？
解題思路
這道題考查的是二分查找睦刃。
代碼實現(xiàn)
class Solution {
public int search(int[] nums, int target) {
int left = 0, right = nums.length -1,index = -1;
while(left <= right){
int mid = left + (right - left) / 2;
if(nums[mid] == target){
index = mid;
break;
}
//mid的左、右兩個區(qū)間一定至少有一個是升序排列的
if(nums[mid] >= nums[left]){
//左側升序
if(nums[mid] > target && nums[left] <= target){
//并且target在此范圍內十酣，則搜索區(qū)間一定在左側
right = mid - 1;
}else{
left = mid + 1;
}
}else{
if(nums[mid] < target && nums[right] >= target){
left = mid + 1;
}else{
right = mid -1;
}
}
}
return index;
}
}
