二分查找
题目
给定一个 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]之间。
初见思路
虽然这套题有明确的考察点，但是我习惯拿到题先用最笨的办法实现一次，然后再改进算法
这题整体还是比较简单的，如果用常规的思路也很容易做出来
例如：遍历数组，找到符合条件的值，然后返回其下标，如果条件均不满足，则返回默认下标值（-1）
class Solution {
public int search(int[] nums, int target) {
int index = -1;
for(int i = 0; i < nums.length; i++){
if(nums[i] == target){
index = i;
}
}
return index;
}
}
那么实际上，本题考察的主要是“查找”数组的过程
显然，遍历的方式对于二分法来说，是非常低效的，因此肯定是要用二分法来写的
常规思路
在升序数组nums中寻找目标值target，对于特定下标 i，比较nums[i]和target的大小
- 如果nums[i] = target，则下标 i 即为要寻找的下标;
- 如果nums[i] > target，则 target 只可能在下标 i 的左侧;
- 如果nums[i] < target，则target只可能在下标 i 的右侧。
基于上述事实，可以在有序数组中使用二分查找寻找目标值。【ps：如果数组是乱序，那么有你可能会找出多个值】
二分法的解题流程如下：
1、定义一个查找的范围，一般用left和right代表左右边界
2、在该范围内取中点middle，比较nums[mid]和target
3、根据比较结果进行返回或继续对某侧进行查找
解题模板
实际上二分法有两种写法，分别是左闭右闭和左闭右开【即是否包含边界点本身】，模板只记一种就行，另外的补充再说
Java版
class Solution {
public int search(int[] nums, int target) {
//①定义左右边界
int left = 0, right = nums.length - 1;
//②写一个条件循环*
while (left <= right) {
//计算区间的中点mid
int mid = (right - left) / 2 + left;//用减是为了防止数据溢出，加left是为了定位到当前区间
if (nums[mid] == target) {
return mid;
} else if (nums[mid] > target) { //此时，target只能在区间中点的左半部分，因此右边界改变，变为左半部分的右边界
right = mid - 1;
} else if(nums[mid] < target) {//target只能在区间中点的右半部分，因此左边界改变，变为右半部分的左边界
left = mid + 1;
}
}
return -1;//找不到返回-1
}
}
注释：
边界问题
在上述写法中有两处值得关注的边界，
一处是while的条件left <= right【什么时候要写<、什么时候写<=】，一处是边界改变时的mid - 1【什么时候写mid，什么时候写mid-1】
这两个边界问题都只取决于你决定采用哪种二分法的写法，在一开始我们就必须先确定要用左闭右闭还是左闭右开，然后后面再写的时候要贯彻执行，根据区间的定义去选择边界
以左闭右闭[left, right]为例
当忘了while里应该写<=还是<时，可以想一想一开始确定的区间
比如，如果我写left <= right，对于[left, right]来说是不是合法的呢？【[1,1]，1到1的区间且包含1，虽然只有一个元素但至少不非法】
显然还是可以这么写的，所以在左闭右闭时应该写left <= right
类似的，left <= right对于[left, right)则不合法【[1,1)，即包含1又不含1？】
那么mid呢？
假设目前你的nums[mid] > target，那么这个target一定不会出现在当前mid的右边区间了
所以下一步应该从左边区间再查找
这时候应该将当前的右边界调整到左边区间上来，并且需要排除掉当前的nums[mid]
因此下次查找的右边界的下标应该是right = mid - 1
如果不减1就相当于把一个不属于下次查找区间的数放到区间中了，对于区间来说是非法的，自然会出错
类似的，right = mid - 1对于[left, right)则不合法，因为[left, right)在下次查找中本来就不包含right，所以应该直接写right = mid【若nums[mid] < target，则[left, right)的left还是需要写成left = mid - 1，因为left在[left, right)中是被包括在内的】
Python版
class Solution:
def search(self, nums: List[int], target: int) -> int:
left, right = 0, len(nums) - 1
while left <= right:
mid = (right - left)//2 + left
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
拓展练习
LeetCode35搜索插入位置
思路就是二分查找，这里还是选左闭右闭的方式去写
Java版
class Solution {
public int searchInsert(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while(left <= right){
int mid = (right - left)/2 + left;
if(nums[mid] == target){
return mid;
}else if(nums[mid] < target){
left = mid + 1;
}else{
right = mid - 1;
}
}
//此处可以同时处理四种情况下的返回值
//1、目标值等于数组中某一个元素 return middle;
//2、目标值插入数组中的位置 [left, right]，return right + 1
//3、目标值在数组所有元素之后的情况 [left, right]，这是右闭区间，所以 return right + 1
//4、目标值在数组所有元素之前 [0, -1]【没想通】
return right+1;
}
}
Python版
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
left, right = 0, len(nums)-1
while left <= right:
mid = (right - left)//2 + left
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return right+1
