网络异常，图片无法展示
|
题目描述
这是 LeetCode 上的 704. 二分查找 ，难度为 简单。
Tag : 「二分」
给定一个 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]之间。
二分
一道二分裸题，写二分重点在于学会从「二段性」出发进行分析，想清楚二分的是哪个端点/边界。
而不是局限于用什么模板，大于还是小于，硬记这些会理解二分不会有任何帮助。
事实上，当搞清楚二分的内容之后，何种形式写法都能写出。
代码：
class Solution { public int search(int[] nums, int t) { int n = nums.length; int l = 0, r = n - 1; while (l < r) { int mid = l + r + 1 >> 1; if (nums[mid] <= t) l = mid; else r = mid - 1; } return nums[r] == t ? r : -1; } } 复制代码
class Solution { public int search(int[] nums, int t) { int n = nums.length; int l = 0, r = n - 1; while (l < r) { int mid = l + r >> 1; if (nums[mid] >= t) r = mid; else l = mid + 1; } return nums[r] == t ? r : -1; } } 复制代码
- 时间复杂度：O(\log{n})O(logn)
- 空间复杂度：O(1)O(1)
最后
这是我们「刷穿 LeetCode」系列文章的第 No.704 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
