这是悦乐书的第297次更新，第316篇原创
01 看题和准备
今天介绍的是LeetCode算法题中Easy级别的第165题（顺位题号是704）。给定n个元素的排序（按升序）整数数组nums和目标值，编写一个函数来搜索nums中的目标。如果target存在，则返回其索引，否则返回-1。例如：
输入：nums = [-1,0,3,5,9,12]，目标= 9
输出：4
说明：9存在于nums中，其索引为4
输入：nums = [-1,0,3,5,9,12]，target = 2
输出：-1
说明：2在nums中不存在，因此返回-1
注意：
nums中的所有元素都是唯一的。
n将在[1,10000]范围内。
nums中每个元素的值将在[-9999,9999]范围内。
本次解题使用的开发工具是eclipse，jdk使用的版本是1.8，环境是win7 64位系统，使用Java语言编写和测试。
02 第一种解法
使用二分查找。取数组的第一位和最后一位索引值，计算取出中间数做新索引，判断新索引对应的元素是否等于目标值，等于就直接返回新索引，小于就将开始索引重新赋值为中间索引加1，大于就将结束索引重新赋值为中间索引减1。
此解法的时间复杂度是O(log2(n))，空间复杂度是O(1)。
public int search(int[] nums, int target) {
if (target < nums[0] || target > nums[nums.length-1]) {
return -1;
}
int start = 0, end = nums.length-1;
while (start <= end) {
int mid = (end+start)/2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] > target) {
end = mid-1;
} else {
start = mid+1;
}
}
return -1;
}
03 第二种解法
直接使用循环依次匹配，如果遍历完数组所有元素都没有匹配上，就返回-1。
此解法的时间复杂度是O(n)，空间复杂度是O(1)。
public int search(int[] nums, int target) {
if (target < nums[0] || target > nums[nums.length-1]) {
return -1;
}
for (int i=0; i<nums.length; i++) {
if (target == nums[i]) {
return i;
}
}
return -1;
}
04 第三种解法
因为数组元素的取值范围定了，我们可以使用新的数组，以旧数组元素值为索引，旧元素索引为值，最后以目标值为索引，在新数组中查找，如果其值为0，就返回-1，反之返回其值。
此解法的时间复杂度是O(n)，空间复杂度是O(n)。
public int search(int[] nums, int target) {
if (target < nums[0] || target > nums[nums.length-1]) {
return -1;
}
int[] temp = new int[20000];
for (int i=0; i<nums.length; i++) {
temp[nums[i]+10000] = i+1;
}
return temp[target+10000] == 0 ? -1 : temp[target+10000]-1;
}
05 小结
算法专题目前已日更超过四个月，算法题文章165+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。
以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！
