二分法的使用
旋转数组：
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。你可以假设数组中不存在重复的元素。
你的算法时间复杂度必须是 O(log n) 级别。
输入: nums = [4,5,6,7,0,1,2], target = 0 输出: 4
class Solution {
int[] nums;
int target;
/**
* 寻找拐点的方法，二分法寻找，本来应该是依次递增的，出现右边小于左边的收，就说明拐点就在这个范围内进行定位
* @param left
* @param right
* @return 返回的是拐点的值
*/
public int find_rotate_index(int left,int right){
if(nums[left] <nums[right]){
return 0;
}
while(left<=right){
int pivot = (left+right)/2;
if(nums[pivot]>nums[pivot+1] ){
return pivot +1;
}
else{
if(nums[pivot]<nums[left]){
right = pivot-1;
}else{
left = pivot +1;
}
}
}
return 0;
}
/**
* 二分法查找目标
* @param left
* @param right
* @return
*/
public int search(int left,int right){
while(left<=right) {
int pivot = (right+left)/2;
if(nums[pivot] == target) {
return pivot;
}else if(nums[pivot]>target) {
right = pivot-1;
}else {
left = pivot+1;
}
}
return -1;
}
public int search(int[] nums, int target) {
this.nums = nums;
this.target = target;
int n = nums.length;
if(n ==0) {
return -1;
}
if(n == 1) {
return this.nums[0] == target?0:-1;
}
int rotate_index = find_rotate_index(0,n-1);
//特俗情况处理
if(rotate_index == 0) {
return search(0, n-1);
}
if(nums[rotate_index] == target)return rotate_index;
//比较目标值和拐点那个大来判断用前半段函数还是后半段函数
// 456123
if(target >= nums[0]) {
//说明是前半截
return search(0,rotate_index);
}
return search(rotate_index+1,n-1);
}
}
在排序数组中查找元素的第一个和最后一个位置
上述的题目是通过二分法 先找到扭转的，然后在通过二分法找到目标值。
这个题目是直接通过二分法进行判断。
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
你的算法时间复杂度必须是 O(log n) 级别。
如果数组中不存在目标值，返回 [-1, -1]。
示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]
示例 2:
输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]
1、暴力算法
先写一个暴力算法，估计大家都会的：
/**
* @param nums 给定的数组，一个一个进行比较
* @param target 目标值
* @return
*/
public int[] searchRange(int[] nums, int target) {
int begin = -1, end = -1, n = nums.length;
for (int i = 0; i <= n - 1; i++) {
if (nums[i] == target) {
begin = i;
while (++i <= n - 1 && nums[i] == target) {
System.out.println(i);
}
end = i - 1;
break;
}
}
end = end > begin ? end : begin;
return new int[] { begin, end };
}
2、二分法算法
这个方法分三步，第一步，通过二分法随便找到一个值，根据第一部返回的值，将数组分为两部分，左边的找左边界，右边的找右边界，就是第二三部
/**
* 题目要求log n的算法，上述的算法有问题，需要优化，由于是已经排序的，首先想到的是二分法
* 通过二分法找到目标账号的数字，然后继续通过二分法找左边界和有边界
*
* @param nums
* @param target
* @return
*/
public int[] searchRange2(int[] nums, int target) {
int n = nums.length;
int left = 0, right = n - 1, tempVal = -1;
int begin = -1, end = -1;
while (right >= left) {
// 中间数
int pivot = (right + left) / 2;
if (nums[pivot] == target) {
// 开始第二次二分处理
tempVal = pivot;
break;
}
if (nums[pivot] > target) {
right = pivot - 1;
} else {
left = pivot + 1;
}
}
//以tempVal为中心划分两个数组，然后分别找左边界和有边界
if (tempVal == -1) {
return new int[] { begin, end };
} else {
// 先找开始
left = 0;
right = tempVal;
while (left <= right) {
int pivot = (right + left) / 2;
if (nums[pivot] == target) {
if (pivot == 0 || nums[pivot] != nums[pivot - 1]) {
begin = pivot;
break;
} else {
right = pivot - 1;
}
} else {
left = pivot + 1;
}
}
// 然后找结束
left = tempVal;
right = n - 1;
while (left <= right) {
int pivot = (right + left) / 2;
if (nums[pivot] == target) {
if (pivot == n - 1 || nums[pivot] != nums[pivot + 1]) {
end = pivot;
break;
} else {
left = pivot + 1;
}
} else {
right = pivot - 1;
}
}
}
return new int[] { begin, end };
}
3、优化二分法代码
我们可以看到上述的方法中，寻找左边界，和寻找有边界的方法基本一致，我们可以考虑将其抽离成一个方法，优化代码结构
/**
* 题目要求log n的算法，上述的算法有问题，需要优化，由于是已经排序的，首先想到的是二分法
* 通过二分法找到目标账号的数字，然后继续通过二分法找左边界和有边界
*
* @param nums
* @param target
* @return
*/
public int[] searchRange2(int[] nums, int target) {
int n = nums.length;
int left = 0, right = n - 1, tempVal = -1;
int begin = -1, end = -1;
while (right >= left) {
// 中间数
int pivot = (right + left) / 2;
if (nums[pivot] == target) {
// 开始第二次二分处理
tempVal = pivot;
begin = extremeInsertionIndex(nums, target, tempVal, true);
end = extremeInsertionIndex(nums, target, tempVal, false) - 1;
break;
}
if (nums[pivot] > target) {
right = pivot - 1;
} else {
left = pivot + 1;
}
}
if (begin > tempVal || left == -1) {
begin= tempVal;
} else if (end< left || end> n - 1) {
end= tempVal;
}
return new int[] { begin, end };
}
/**
* 这个方法相比较之前做了一些优化，这里左边界返回的还是左边界，右边界返回的是右边再往右一格的
* @param nums 搜索的数组
* @param target 搜索的目标值
* @param tempVal 中间分割的字段（也就是随便一个目标值所对应的下标）
* @param isLeft 是否找的是开始位置，true返回的是左边界，false返回的是右边界
* @return
*/
private int extremeInsertionIndex(int[] nums, int target, int tempVal, boolean isLeft) {
int left, right, n = nums.length;
if (isLeft) {
left = 0;
right = tempVal;
} else {
left = tempVal;
right = n - 1;
}
while (left <= right) {
int pivot = (right + left) / 2;
if (nums[pivot] > target || isLeft && nums[pivot] == target) {
// 中间数大于目标值的时候,中间数等于目标值的时候，左边的时候，改变的是right 右边的时候，改变的是left
right = pivot - 1;
} else {// z中间的数，小于目标值的时候，连个都是改左边的值。
// 中间数等于目标值的时候，左半部分改变的是right 右半部分，改变的是left
left = pivot + 1;
}
}
return left;
}
