今日主题，二分查找。
- 计算mid的时候需要防止溢出，当left和right太大时，
mid = ( left + right ) / 2有可能会移除，因此，最好使用mid = left + ( right - left ) / 2。
704. 二分查找
问题描述
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
解题思路
采用两端都闭合的搜索区间[left，right]实现。
代码实现
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左侧,搜索区间变为[left, mid - 1]
right = mid - 1;
}else if(nums[mid] < target){
//target在mid右侧,搜索区间变为[mid + 1, right]
left = mid + 1;
}else{
//找到了target, 结束循环
index = mid;
break;
}
}
return index;
}
}
34. 在排序数组中查找元素的第一个和最后一个位置
问题描述
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
解题思路
用两次二分查找，分别找到target在数组中的左右边界即可。
代码实现
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)找出给定目标值在数组中的开始位置，目标值不存在则返回-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左侧,搜索区间变为[left, mid - 1]
right = mid - 1;
}else if(nums[mid] < target){
//target在mid右侧,搜索区间变为[mid + 1, right]
left = mid + 1;
}else{
//nums[mid] == target不返回，继续向左搜索左边界
right = mid - 1;
}
}
//循环结束时，left = right + 1。
if(left >= nums.length || nums[left] != target){
//如果所有元素都小于target，则left会越界
return -1;
}
return left;
}
//(2)找出给定目标值在数组中的结束位置，目标值不存在则返回-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左侧,搜索区间变为[left, mid - 1]
right = mid - 1;
}else if(nums[mid] < target){
//target在mid右侧,搜索区间变为[mid + 1, right]
left = mid + 1;
}else{
//nums[mid] == target不返回，继续向右搜索右边界
left = mid + 1;
}
}
//循环结束时，right = left - 1。
if(right < 0 || nums[right] != target){
//如果所有元素都大于target，则right会越界
return -1;
}
return right;
}
}
33. 搜索旋转排序数组
问题描述
整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的索引，否则返回 -1 。
你能设计一个时间复杂度为 O(log 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的左、右两个区间一定至少有一个是升序排列的
if(nums[mid] >= nums[left]){
//左侧升序
if(nums[mid] > target && nums[left] <= target){
//并且target在此范围内，则搜索区间一定在左侧
right = mid - 1;
}else{
left = mid + 1;
}
}else{
if(nums[mid] < target && nums[right] >= target){
left = mid + 1;
}else{
right = mid -1;
}
}
}
return index;
}
}
