一孽尽、旋轉(zhuǎn)數(shù)組中的最小數(shù)字
題目：把一個(gè)數(shù)組最開(kāi)始的若干個(gè)元素搬到數(shù)組的末尾田巴，我們稱(chēng)之為數(shù)組的旋轉(zhuǎn)麸折。輸入一個(gè)遞增排序的數(shù)組的旋轉(zhuǎn)锡凝，輸出旋轉(zhuǎn)數(shù)組的最小元素。例如磕谅，數(shù)組 [3,4,5,1,2] 為 [1,2,3,4,5] 的一個(gè)旋轉(zhuǎn)私爷，該數(shù)組的最小元素為1雾棺。
解法一：順序查找，復(fù)雜度O(n)
var search = function(nums){
var min = nums[0];
for(var i=1;i<nums.length;i++){
if(nums[i]<=min){
min = nums[i];
}
}
return min;
}
解法二：二分查找衬浑，復(fù)雜度O(logn)
var search = function(nums){
var left = 0,
right = nums.length-1,
mid = 0;
while(right-left > 1 && nums[right] <= nums[left]){
mid = parseInt((left+right)/2);
// 左區(qū)間是遞增序列捌浩，最小元素在右區(qū)間
if(nums[left]<=nums[mid]){
left = mid;
}
// 右區(qū)間是遞增序列，最小元素在左區(qū)間
if(nums[mid]<=nums[right]){
right = mid;
}
}
return nums[right];
}
二工秩、搜索旋轉(zhuǎn)數(shù)組中的元素
題目：在旋轉(zhuǎn)數(shù)組中搜索一個(gè)給定的目標(biāo)值尸饺，如果數(shù)組中存在這個(gè)目標(biāo)值，則返回它的索引助币，否則返回 -1 浪听。假定數(shù)組中沒(méi)有重復(fù)元素。
思路：二分查找眉菱，復(fù)雜度O(logn)
取區(qū)間的中間值mid后：
- 如果nums[mid] == target迹栓，直接返回mid值；
- 如果nums[mid] >= nums[left]俭缓，說(shuō)明左半?yún)^(qū)間是遞增序列克伊；如果target落在左半?yún)^(qū)間，則在左半?yún)^(qū)間內(nèi)搜索华坦，否則在右半?yún)^(qū)間內(nèi)搜索
- 如果nums[mid] <= nums[left]愿吹，說(shuō)明右半?yún)^(qū)間是遞增序列；如果target落在右半?yún)^(qū)間惜姐，則在右半?yún)^(qū)間內(nèi)搜索犁跪，否則在左半?yún)^(qū)間內(nèi)搜索
var search = function(nums,target){
var left = 0,
right = nums.length-1,
mid = 0;
if(nums.length == 0) return -1;
while(right >= left){
mid = parseInt((left+right)/2);
if(nums[mid] == target) return mid;
// 左半?yún)^(qū)間是遞增序列
if(nums[left] <= nums[mid]){
if(nums[left] <= target && target < nums[mid]){
right = mid-1;
}else{
left = mid+1;
}
}else{ //右半?yún)^(qū)間是遞增序列
if(nums[mid] < target && target <= nums[right]){
left = mid+1;
}else{
right = mid-1;
}
}
}
return -1;
}
三、搜索旋轉(zhuǎn)數(shù)組中的元素
題目：在旋轉(zhuǎn)數(shù)組中搜索一個(gè)給定的目標(biāo)值歹袁，如果數(shù)組中存在這個(gè)目標(biāo)值坷衍，則返回true，否則返回false宇攻。數(shù)組中可能存在重復(fù)元素惫叛。
思路：二分查找，復(fù)雜度O(logn)
思路基本同上題逞刷，只是要考慮到[1,0,1,1,1] 和 [1,1,1,0,1]的情況：
- 如果nums[mid] == target，直接返回mid值妻熊；
- 如果nums[left] == nums[mid]夸浅，無(wú)法判斷遞增區(qū)間的位置，則需要將left++扔役，去掉干擾元素帆喇；
- 如果nums[mid] >= nums[left]，說(shuō)明左半?yún)^(qū)間是遞增序列亿胸；如果target落在左半?yún)^(qū)間坯钦，則在左半?yún)^(qū)間內(nèi)搜索预皇，否則在右半?yún)^(qū)間內(nèi)搜索
- 如果nums[mid] <= nums[left]，說(shuō)明右半?yún)^(qū)間是遞增序列婉刀；如果target落在右半?yún)^(qū)間吟温，則在右半?yún)^(qū)間內(nèi)搜索，否則在左半?yún)^(qū)間內(nèi)搜索
var search = function(nums, target) {
var left = 0,
right = nums.length-1,
mid = 0;
if(nums.length == 0) return false;
while(right >= left){
mid = parseInt((left+right)/2);
if(nums[mid] == target) return true;
// 去掉重復(fù)項(xiàng)的干擾
if(nums[left] == nums[mid]){
left++;
continue;
}
if(nums[left] <= nums[mid]){
if(nums[left] <= target && target < nums[mid]){
right = mid-1;
}else{
left = mid+1;
}
}else{
if(nums[mid] < target && target <= nums[right]){
left = mid+1;
}else{
right = mid-1;
}
}
}
return false;
};
