力扣14天算法入门_Day_1_704.二分查找

力扣14天算法入门_Day_1_704.二分查找
二分查找，顾名思义就是设立左右边界后，查找左右边界的中间值是否为所求值。
例题：
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-search

首先，设立初始左右边界，left = 0，right = nums.length - 1，中间值mid则为（left + right）/ 2¹（此处改为 left + （right - left）/ 2 原因在下面）。
接下来就是在左边界小于有边界的前提下比对nums[mid]和target是否相同，有三种情况：

1. nums[mid] = target，直接返回mid
2. nums[mid] > target，中间值比目标值要大，那么将右边界左移，right = mid - 1
3. nums[mid] < target，中间值小于目标值，那么将左边界右移，left = mid + 1

Java代码如下：

class Solution {
    public int search(int[] nums, int target) {
		int left = 0,right = nums.length - 1;
		while(left <= right){
			int mid = (left + right) / 2;
			if(nums[mid] = target){
				return mid;
			}else if(nums[mid] < target){
				left = mid + 1;
			}else{
				right = mid - 1;
			}
		}
		return -1;
    }
}

---

1. 看了其他大佬的解题思路，他们的中间值为mid = left + (right - left) / 2，还没搞清楚之间的区别，弄明白后回来补上。补充：当left和right都很大时，两者直接相加容易溢出导致时间超出限制，故使用left + (right - left) / 2 ↩︎