代码随想录算法练习Day1:二分查找

题目链接：704. 二分查找

卡哥视频讲解：手把手带你撕出正确的二分法 | 二分查找法 | 二分搜索法 | LeetCode：704. 二分查找

二分法概述：

二分法（Binary Search）是一种在有序数组或列表中查找目标元素的算法。

二分法使用前提：

1. 有序数组或列表：二分法要求在查找的数据结构中元素按照某种顺序有序排列，通常是升序排列。如果数组或列表没有排序，需要先对其进行排序，否则无法使用二分法进行查找。

2. 目标元素存在：二分法适用于在有序数组或列表中查找目标元素是否存在，或者查找目标元素的位置。如果目标元素不在数组或列表中，二分法无法成功找到目标元素。

3. 随机访问：二分法要求能够通过索引或指针以O(1)的时间复杂度访问数组或列表的任意位置。这通常意味着数据结构需要支持随机访问，比如数组。

代码示例：

示例1（左闭右闭写法）：​​​​​​​

示例2（左闭右开写法）：

总结：

1.>> 是右移位操作符，它将左操作数向右移动指定的位数。在这里，right - left 表示当前搜索范围的长度，right - left >> 1 将长度右移一位，相当于将长度除以2，得到搜索范围的一半。然后再加上 left，得到中间位置 mid。

这种写法与普通的 (left + right) / 2 求中间位置的写法相比，可以避免在大数相加时可能导致的溢出问题，同时也更为高效。因为右移位操作符的性能比除法运算更高，尤其在一些硬件上会被优化为位运算。

2.在写范围的时候，是根据是否包含数组的边界元素来确定的。