題目:有一個(gè)長(zhǎng)度為 n 的按嚴(yán)格升序排列的整數(shù)數(shù)組 nums ，在實(shí)行 search 函數(shù)之前，在某個(gè)下標(biāo) k 上進(jìn)行旋轉(zhuǎn)，使數(shù)組變?yōu)閇nums[k],nums[k+1],.....,nums[nums.length-1],nums[0],nums[1],.......,nums[k-1]]。給定旋轉(zhuǎn)后的數(shù)組 nums 和一個(gè)整型 target ，請(qǐng)你查找 target 是否存在于 nums 數(shù)組中并返回其下標(biāo)（從0開(kāi)始計(jì)數(shù)），如果不存在請(qǐng)返回-1。數(shù)據(jù)范圍： 1000000≤n≤10000，0≤target≤100000要求：空間復(fù)雜度 O(1) ，時(shí)間復(fù)雜度 O(n)
//簡(jiǎn)單查找import java.util.*;public class Solution { /** * 代碼中的類(lèi)名、方法名、參數(shù)名已經(jīng)指定，請(qǐng)勿修改，直接返回方法規(guī)定的值即可 * * * @param nums int整型一維數(shù)組 * @param target int整型 * @return int整型 */ public int search (int[] nums, int target) { for(int i=0;i<=nums.length-1;i++){ if(nums[i] == target){ return i; } } return -1; }}
二分查找分析:如果給定的數(shù)組是排序好的數(shù)組，那么直接用二分法查找即可。但所給的數(shù)組是排序數(shù)組旋轉(zhuǎn)后的數(shù)組，由兩部分有序的部分組成。是否可以用二分法？既然所給的數(shù)組修改了一下，那么也對(duì)二分查找進(jìn)行修改一下。假設(shè)從left到k，k+1到right為兩個(gè)有序部分，mid一定位于（left，k）（k+1，right）兩個(gè)區(qū)間之內(nèi)，那么（left，mid）和（mid，right）這兩個(gè)區(qū)間必定有一個(gè)是有序的，我們可以通過(guò)比較numsp[left]和nums[mid],nums[right]之間的大小關(guān)系得到那個(gè)區(qū)間有序假設(shè)（left，mid）這段區(qū)間有序，如果有target>mid,那么區(qū)間（left，mid）就應(yīng)該被舍棄，下一步搜索區(qū)間為(mid+1,right)如果targetarget，區(qū)間（left，mid）也應(yīng)該被舍棄,下一步搜索區(qū)間為(mid+1,right)如果target
//二分查找import java.util.*;public class Solution { /** * 代碼中的類(lèi)名、方法名、參數(shù)名已經(jīng)指定，請(qǐng)勿修改，直接返回方法規(guī)定的值即可 * * * @param nums int整型一維數(shù)組 * @param target int整型 * @return int整型 */ public int search (int[] nums, int target) { int left = 0,right = nums.length-1; int mid; while(left<=right){ mid = left+(right-left)/2; if(nums[mid]==target){ return mid; } if(nums[mid]>=nums[left]){ //如果從left到mid有序 if(target>nums[mid]||(targetnums[mid]&&target>nums[right])){ right = mid; } else{ left = mid+1; } } } return -1; }}
