一、題目描述
給定一個 n 個元素有序的（升序）整型數組 nums 和一個目标值 target ，寫一個函數搜尋 nums 中的 target，如果目标值存在傳回下标，否則傳回 -1。
示例 1:
輸入: nums = [-1,0,3,5,9,12], target = 9
輸出: 4
解釋: 9 出現在 nums 中并且下标為 4
示例 2:
輸入: nums = [-1,0,3,5,9,12], target = 2
輸出: -1
解釋: 2 不存在 nums 中是以傳回 -1 複制
提示：
你可以假設 nums 中的所有元素是不重複的。
n 将在 [1, 10000]之間。
nums 的每個元素都将在 [-9999, 9999]之間。
二、解題思路
在升序數組 nums 中尋找目标值 target，對于特定下标 i，比較 nums[i] 和target 的大小：
如果 nums[i]=target，則下标 i 即為要尋找的下标；
如果nums[i]>target，則 target 隻可能在下标 i 的左側；
如果nums[i]<target，則target 隻可能在下标 i 的右側。
基于上述事實，可以在有序數組中使用二分查找尋找目标值。
二分查找的做法是，定義查找的範圍[left,right]，初始查找範圍是整個數組。每次取查找範圍的中點 mid，比較 nums[mid] 和target 的大小，如果相等則mid 即為要尋找的下标，如果不相等則根據 nums[mid] 和target 的大小關系将查找範圍縮小一半。
由于每次查找都會将查找範圍縮小一半，是以二分查找的時間複雜度是O(logn)，其中 n 是數組的長度。
二分查找的條件是查找範圍不為空，即 left≤right。如果 target 在數組中，二分查找可以保證找到 target，傳回target 在數組中的下标。如果target 不在數組中，則當 left>right 時結束查找，傳回 -1。
三、代碼
public class Solution {
public int search(int[] nums, int target) {
int low=0;
int high=nums.length-1;
while(low<=high){
int mid=(low+high)/2;
if(nums[mid]==target){
return mid;
}
if(nums[mid]<target){
low=mid+1;
}
if(nums[mid]>target){
high=mid-1;
}
}
return -1;
}
public static void main(String[] args) {
int[] nums={-1,0,3,5,9,12};
Solution solution=new Solution();
System.out.println(solution.search(nums,2));
}
} 複制
四、複雜度分析
時間複雜度：O(logn)，其中 n 是數組的長度。
空間複雜度：O(1)。