算法Day1|704. 二分查找、27. 移除元素

刷题���一天。毫无头绪。加油！

---

704.二分查找

题目链接：https://leetcode.cn/problems/binary-search/

文章讲解：https://programmercarl.com/0704.%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.html

视频讲解：https://www.bilibili.com/video/BV1fA4y1o715

题目：

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

 

二分查找：

1.条件：（1）查找的内容逻辑上是有序的；

              （2）查找的内容只能有一个。

2.查找区间的范围方式：（1）左闭右闭  [left , right]

                                        （2）左闭右开 [left , right)

3.数组长度是奇数或者偶数，都不影响算法如何排除的问题。

4.真正影响的是 中间的那个数字是否应该加入下一次的查找中，即边界问题。

相关知识学习参考以下链接：【二分查找】详细图解_二分查找法流程图-CSDN博客https://blog.csdn.net/qq_45978890/article/details/116094046

二分法思想：

整个数组是有序的，数组默认为递增，并且查找的数字是唯一的。

1.首先找到数组中心点mid的值，与目标值val比较大小；

2.（1）如果中心值mid等于目标值val，输出中心值mid；

   （2）中心值mid小于目标值val，那么val位于数组的右半部分，则中间值mid左边的所有数字都小于目标值，全部排除；

   （3） 中心值mid大于目标值val，那么val位于数组的左半部分，则中间值mid右边的所有数字都大于目标值，全部排除；

解答：

分为两种，左闭右闭 和 左闭右开。

代码的重点是关注 区间的边界问题。

1.左闭右闭 [ left , right ]

        left = 0 ; right = size - 1;

        这种情况下，区间就是 左闭右闭，那么此时的循环条件就是 while (left