二分法:
1.原理：
在升序數(shù)組 nums 中尋找目標(biāo)值nums[i]，對于特定下標(biāo) i，比較nums[i] 和target 的大?。?/p>
? 如果 nums[i] = target ，則下標(biāo) i 即為要尋找的下標(biāo)；
如果? nums[i] > target，則 target 只可能在下標(biāo) i 的左側(cè)；
如果? nums[i] < target，則 target只可能在下標(biāo) i 的右側(cè)。
基于上述事實，可以在有序數(shù)組中使用二分查找尋找目標(biāo)值。
二分查找的做法是，定義查找的范圍[left,right]，初始查找范圍是整個數(shù)組。每次取查找范圍的中點mid，比較 nums[mid] 和 target 的大小，如果相等則 mid 即為要尋找的下標(biāo)，如果不相等則根據(jù) nums[mid] 和target 的大小關(guān)系將查找范圍縮小一半。
? 由于每次查找都會將查找范圍縮小一半，因此二分查找的時間復(fù)雜度是 O(logn)，其中 n是數(shù)組的長度。
? ? ? 一般獲取數(shù)組中點的方法為：
intmid=left+(right-left)/2;
這樣做的好處是可以防止數(shù)據(jù)過大，超過int的界限。
2.代碼實現(xiàn):
? ? ? intleft=0;
intright=nums.length-1;
intmid=left+(right-left)/2;
while(left<=right){
if(nums[mid]==target){
returnmid;
}
if(nums[mid]>target){
right=mid-1;
intmid=left+(right-left)/2;
? ? ? ? ? ? ? //目標(biāo)值小于nums[mid],變化右邊界值，縮小范圍
}
if(nums[mid]<target){
left=mid+1;
intmid=left+(right-left)/2;
? ? ? ? ? ? ? ? ? //目標(biāo)值小于nums[mid],變化左邊界值，縮小范圍
}
}
return-1;
