Given a sorted (in ascending order) integer array nums
of n
elements and a target
value, write a function to search target
in nums
. If target
exists, then return its index, otherwise return -1
.
Example 1:
Input:nums
= [-1,0,3,5,9,12],target
= 9 Output: 4 Explanation: 9 exists innums
and its index is 4
Example 2:
Input:nums
= [-1,0,3,5,9,12],target
= 2 Output: -1 Explanation: 2 does not exist innums
so return -1
Note:
- You may assume that all elements in
nums
are unique. n
will be in the range[1, 10000]
.- The value of each element in
nums
will be in the range[-9999, 9999]
.
二分查找 时间复杂度O(lgn)
public int search(int[] nums, int target) { if(null==nums||0==nums.length){ return -1; } int left = 0; int right = nums.length-1; while(left<= right){ int mid = (left+right)/2; if(nums[mid] == target){ return mid; } else if(nums[mid] >target){ right = mid-1; } else{ left = mid+1; } } return -1; }
递归
public int search(int[] nums, int target) { if(null==nums||0==nums.length){ return -1; } return binaryS(nums,0,nums.length-1,target); } private int binaryS(int[] nums,int left,int right,int target){ if(left>right){ return -1; } int mid = (left+right)/2; if(nums[mid]==target){ return mid; } if(nums[mid]<target){ return binaryS(nums,mid+1,right,target); } return binaryS(nums,left,mid-1,target); }