二分搜索.md

### 二分搜索

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

> 示例 1:
> 
> 输入: nums = [-1,0,3,5,9,12], target = 9
> 输出: 4
> 解释: 9 出现在 nums 中并且下标为 4

##### 技巧：

分析二分查找的一个技巧是：
- 不要出现 else，而是把所有情况用 `if` / `else if` 写清楚
- 这样可以清楚地展现所有细节。

这里我们以`递归`和`非递归`方式，解决面试中的二分搜索题

![在这里插入图片描述](https://user-gold-cdn.xitu.io/2019/10/15/16dce04921aa7fe4?w=757&h=379&f=png&s=22160)

##### 递归
思路很简单：

- 判断起始点是否大于终止点
- 比较 `nums[mid] `与目标值大小
- 如果 `nums[mid] `大，说明目标值 target 在前面
- 反之如果 `nums[mid] `小，说明目标值 target 在前面后面
- 如果既不大也不小，说明相等，则返回`当前位置`

```java
class Solution {
    public int search(int[] nums, int target) {
        return binarySearch(nums, 0, nums.length - 1, target);
    }

    private int binarySearch(int[] nums, int start, int end, int target) {
        if(start > end) {
            return -1;
        }
        int mid = (end + start) / 2;
        if(nums[mid] < target) {
            return binarySearch(nums, mid + 1, end, target);
        }
        if(nums[mid] > target) {
            return binarySearch(nums, start, mid - 1, target);
        }
        return mid;
    }
}
```

##### 非递归

这个场景是最简单的:
- 搜索一个数
- 如果存在, 返回其索引
- 否则返回 -1

```java
int binarySearch(int[] nums, int target) {
    int left = 0; 
    // 注意减 1
    int right = nums.length - 1; 

    while(left <= right) {
        int mid = (right + left) / 2;
        if(nums[mid] == target)
            return mid; 
        else if (nums[mid] < target)
            left = mid + 1; // 注意
        else if (nums[mid] > target)
            right = mid - 1; // 注意
        }
    return -1;
}
```

##### 相关视频
[分钟教你二分查找(python版)](https://www.bilibili.com/video/av52404595?from=search&seid=9011867842171109670)

<br>
<br>

-----

### X的平方根

计算并返回 x 的平方根，其中 x 是非负整数。

由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

> 示例 2:
>
> 输入: 8
> 输出: 2
> 说明: 8 的平方根是 2.82842..., 
>     由于返回类型是整数，小数部分将被舍去。

##### 解题思路

使用二分法搜索平方根的思想很简单：

- 就类似于小时候我们看的电视节目中的“猜价格”游戏
- 高了就往低了猜
- 低了就往高了猜
- 范围越来越小。

> 注：一个数的平方根最多不会超过它的一半，例如 8 的平方根，8 的一半是 4，如果这个数越大越是如此

##### 注意：

对于判断条件：

- 比如说：我们很容易想当然觉得
- `mid == x / mid` 和 `mid * mid == x` 是等价的，实际却不然
- 比如 mid = 2，x = 5
- 对于 `mid == x / mid` 就是：2 == 2 返回 true
- 而对于 `mid * mid == x` 就是：4 == 5 返回 false


对于边界条件有个坑:

- 要注意此处耍了一下小技巧，在二分左值和右值相差为1的时候就停止查找；因为在这里，有个对中值取整数的操作，在取整后始终有 `start` == `mid` == `end`则会死循环。

取整操作的误差为1，故而在这里限制条件改成包含1在内的范围`start + 1 < end` ; 这里减一很精髓

```java
public int sqrt(int x) {
    if (x < 0)  {
        throw new IllegalArgumentException();
    } else if (x <= 1) {
        return x;
    }

    int start = 1, end = x;
    // 直接对答案可能存在的区间进行二分 => 二分答案
    while (start + 1 < end) {
        int mid = start + (end - start) / 2;
        if (mid == x / mid) {
            return mid;
        }  else if (mid < x / mid) {
            start = mid;
        } else {
            end = mid;
        }  
    }
    
    if (end > x / end) {
        return start;
    }
    return end;
}
```

<br>
<br>

-----