05 August 2008
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:
1
2
3
4
Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4
Example 2:
1
2
3
Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1
Note:
模板要清晰，注意一个元素的情况，澄清题意。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public int search(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return -1;
}
int left = 0, right = nums.length - 1;
while (left + 1 < right) {
// Prevent (left + right) overflow
int mid = left + (right - left) /2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] > target) {
right = mid;
} else {
left = mid;
}
}
// Post-processing:
// End Condition: left + 1 == right
if (nums[left] == target) {
return left;
}
if (nums[right] == target) {
return right;
}
return -1;
}
}
递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public int search(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return -1;
}
return search (nums, target, 0, nums.length - 1);
}
private int search(int[] nums, int target, int low, int high) {
if (low > high) {
return -1;
}
int mid = low + (high - low) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
return search(nums, target, mid + 1, high);
} else {
return search(nums, target, low, mid - 1);
}
}
}