二分法的使用
旋轉(zhuǎn)數(shù)組：
假設(shè)按照升序排序的數(shù)組在預(yù)先未知的某個(gè)點(diǎn)上進(jìn)行了旋轉(zhuǎn)。
( 例如归露，數(shù)組 [0,1,2,4,5,6,7] 可能變?yōu)?[4,5,6,7,0,1,2] )洲脂。
搜索一個(gè)給定的目標(biāo)值，如果數(shù)組中存在這個(gè)目標(biāo)值剧包，則返回它的索引恐锦，否則返回 -1 。你可以假設(shè)數(shù)組中不存在重復(fù)的元素疆液。
你的算法時(shí)間復(fù)雜度必須是 O(log n) 級(jí)別一铅。
輸入: nums = [4,5,6,7,0,1,2], target = 0 輸出: 4
class Solution {
int[] nums;
int target;
/**
* 尋找拐點(diǎn)的方法，二分法尋找枚粘，本來應(yīng)該是依次遞增的馅闽，出現(xiàn)右邊小于左邊的收，就說明拐點(diǎn)就在這個(gè)范圍內(nèi)進(jìn)行定位
* @param left
* @param right
* @return 返回的是拐點(diǎn)的值
*/
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;
}
/**
* 二分法查找目標(biāo)
* @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;
//比較目標(biāo)值和拐點(diǎn)那個(gè)大來判斷用前半段函數(shù)還是后半段函數(shù)
// 456123
if(target >= nums[0]) {
//說明是前半截
return search(0,rotate_index);
}
return search(rotate_index+1,n-1);
}
}
在排序數(shù)組中查找元素的第一個(gè)和最后一個(gè)位置
上述的題目是通過二分法 先找到扭轉(zhuǎn)的馍迄，然后在通過二分法找到目標(biāo)值福也。
這個(gè)題目是直接通過二分法進(jìn)行判斷。
給定一個(gè)按照升序排列的整數(shù)數(shù)組 nums攀圈，和一個(gè)目標(biāo)值 target暴凑。找出給定目標(biāo)值在數(shù)組中的開始位置和結(jié)束位置。
你的算法時(shí)間復(fù)雜度必須是 O(log n) 級(jí)別赘来。
如果數(shù)組中不存在目標(biāo)值现喳，返回 [-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、暴力算法
先寫一個(gè)暴力算法嗦篱，估計(jì)大家都會(huì)的：
/**
* @param nums 給定的數(shù)組冰单，一個(gè)一個(gè)進(jìn)行比較
* @param target 目標(biāo)值
* @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、二分法算法
這個(gè)方法分三步灸促，第一步诫欠，通過二分法隨便找到一個(gè)值，根據(jù)第一部返回的值浴栽，將數(shù)組分為兩部分荒叼，左邊的找左邊界，右邊的找右邊界典鸡，就是第二三部
/**
* 題目要求log n的算法被廓，上述的算法有問題，需要優(yōu)化萝玷，由于是已經(jīng)排序的嫁乘，首先想到的是二分法
* 通過二分法找到目標(biāo)賬號(hào)的數(shù)字，然后繼續(xù)通過二分法找左邊界和有邊界
*
* @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) {
// 中間數(shù)
int pivot = (right + left) / 2;
if (nums[pivot] == target) {
// 開始第二次二分處理
tempVal = pivot;
break;
}
if (nums[pivot] > target) {
right = pivot - 1;
} else {
left = pivot + 1;
}
}
//以tempVal為中心劃分兩個(gè)數(shù)組间护，然后分別找左邊界和有邊界
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;
}
}
// 然后找結(jié)束
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亦渗、優(yōu)化二分法代碼
我們可以看到上述的方法中，尋找左邊界汁尺，和尋找有邊界的方法基本一致法精，我們可以考慮將其抽離成一個(gè)方法，優(yōu)化代碼結(jié)構(gòu)
/**
* 題目要求log n的算法痴突，上述的算法有問題搂蜓，需要優(yōu)化，由于是已經(jīng)排序的辽装，首先想到的是二分法
* 通過二分法找到目標(biāo)賬號(hào)的數(shù)字帮碰，然后繼續(xù)通過二分法找左邊界和有邊界
*
* @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) {
// 中間數(shù)
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 };
}
/**
* 這個(gè)方法相比較之前做了一些優(yōu)化，這里左邊界返回的還是左邊界拾积，右邊界返回的是右邊再往右一格的
* @param nums 搜索的數(shù)組
* @param target 搜索的目標(biāo)值
* @param tempVal 中間分割的字段（也就是隨便一個(gè)目標(biāo)值所對(duì)應(yīng)的下標(biāo)）
* @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) {
// 中間數(shù)大于目標(biāo)值的時(shí)候,中間數(shù)等于目標(biāo)值的時(shí)候拓巧，左邊的時(shí)候斯碌，改變的是right 右邊的時(shí)候，改變的是left
right = pivot - 1;
} else {// z中間的數(shù)肛度，小于目標(biāo)值的時(shí)候傻唾，連個(gè)都是改左邊的值。
// 中間數(shù)等于目標(biāo)值的時(shí)候承耿，左半部分改變的是right 右半部分冠骄，改變的是left
left = pivot + 1;
}
}
return left;
}
