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

提示：

1. 你可以假设 nums 中的所有元素是不重复的。
2. n 将在 [1, 10000]之间。
3. nums 的每个元素都将在 [-9999, 9999]之间。

二分查找解法

1. 定义左右指针，分别指向头尾
2. 根据左右指针计算中间位置下标middle
3. 判断nums[middle]与目标值target的大小
4. 将区间折半，选择左 或 右区间
   • 中值大于目标值：选择左区间，将右指针缩到中间来，即right = middle - 1;
   • 中指小于目标值：选择右区间，将左指针加到中间来，即left = middle + 1;
5. 当nums[middle] == target，返回下标middle
6. 对边界情况进行处理：
   • 空输入
   • 空数组
   • 数组只有一个元素

public class _704二分查找 {

public static void main(String[] args) {

int[] nums1 = {-1, 0, 3, 5, 9, 12}; // target = 9 || 2

int res1 = search(nums1, 9);

int res2 = search(nums1, 2);

System.out.println("res1 = " + res1);

System.out.println("res2 = " + res2);

}

public static int search(int[] nums, int target) {

if (nums == null || nums.length == 0)

return -1;

int left = 0;

int right = nums.length - 1;

while (left <= right) { // 等于 处理只有一个元素的情况

int middle = (left + right) / 2;

if (nums[middle] == target) {

return middle;

} else if (nums[middle] > target) { // 去左边

right = middle - 1;

} else { // 去右边

left = middle + 1;

}

}

return -1;

}

}