704. 二分查找
给定一个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]之间。
方法一:二分查找
思路
定义左右两个指针,左指针开始时指向0,右指针指向末尾,即nums.length-1。再计算一个中间指针mid,它的值即左右指针的中点。
简单的计算方法为(left+right)/2 ,但是有可能左右指针相加会超过int类型的最大值,因此采用left + (right - left) / 2 的计算方法。
比较nums[mid]与target的值,若相等则直接返回mid,否则如果比target大,则右指针等于中间指针mid减一,否则左指针等于中间指针mid加一。
这个过程因该在循环中进行,当找到目标值时直接return返回,没有找到时,一直进行循环,直到left>right。此时即没有结果,返回-1
解题方法
public int search(int[] nums, int target) {
// 如果目标值存在返回下标,否则返回 -1
// 在 [left, right] 区间里查找 target
int left = 0, right = nums.length - 1;
while (left <= right) { ///还有这里 要小于等于,要不然会报数组越界异常。
int mid = left + (right - left) / 2;
// 查询成功条件
if (nums[mid] == target) {
// 找到了,就将目标元素的索引返回
return mid;
} else if (nums[mid] > target) {
// 下一轮搜索区间:[left, mid - 1]
right = mid - 1;
} else {
// 此时:nums[mid] < target
// 下一轮搜索区间:[mid + 1, right]
left = mid + 1;
}
}
return -1;
}
用java实例来验证
public class Main {
public static void main(String[] args) {
int[] nums = {-1, 0, 3, 5, 9, 12};
int target = 9;
System.out.println(search(nums, target));
}
public static int search(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return -1;
}
}
输出:4
方法二:Java的Arrays.binarySearch()方法
需引入包:import java.util.Arrays;
解题方法
int index = Arrays.binarySearch(nums, target);
用java实例来验证
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int[] nums = {-1, 0, 3, 5, 9, 12};
int target = 9;
int index = Arrays.binarySearch(nums, target);
if (index < 0) {
System.out.println(-1);
} else {
System.out.println(index);
}
}
}
输出:4
方法三:递归处理
深化递归的思想,递归要有终止条件和子问题的解法。
示例:
public class Main {
public static void main(String[] args) {
int[] nums = {-1, 0, 3, 5, 9, 12};
int target = 9;
System.out.println(search(nums, target));
}
public static int search(int[] nums, int target) {
return backtrack(0, nums.length - 1, nums, target);
}
private static int backtrack(int left, int right, int[] nums, int target) {
// 先处理递归到底的情况
if (left > right) {
// 不能形成区间,返回 -1 表示没有找到
return -1;
}
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
// 找到了,就将目标元素的索引返回
return mid;
}
if (target > nums[mid]) {
// 既然是有序数组,目标元素的值比中间元素还要大,就应该在中间元素的右边去找
return backtrack(mid + 1, right, nums, target);
}
if (target < nums[mid]) {
// 既然是有序数组,目标元素的值比中间元素还要小,就应该在中间元素的左边去找
return backtrack(left, mid - 1, nums, target);
}
return -1;
}
}
输出:4



