|
二分法:二分法是数学里面较为常见的算法之一，又可以被称为二分查找，它描述了在有序集合中搜索特定值的过程。二分法顾名思义就是一分为二。广义的二分查找是将问题的规模尽可能的缩小到原有的一半。
一般来说，我们都会遇到这种问题：给定一个由数字组成的有序数组，并给你一个数字，请你判断这个数字是否在数组中。
像这类问题我们一般会想到，用这个数字与数组里的数逐个比较，但是这样一来会很麻烦，这个时候就会用到二分法，将数组中的数一分为二，用这个数同分开的中间值相比较，如果大于则将前半段数组中的数舍弃，在后半段数组中再次二分，这样一来，往复循环就可以将数组中的数都判断出来。
所以二分法查找原理：
(1).确定中间值与左右边界的值(下标）
(2).查找的数与中间比较，如果中间值大于要查找的数则往左边查询，反之右边）
(3).判断没有查找到的情况：如果扫描到左边界的元素个数大于右边边界的元素个数，则表示没有找到
注意：一般数组会是无序的，在利用二分法之前应该先进行升序排序或降序排序，然后进行二分法
对于二分查找中使用的术语，这是网上查阅的有关说明
二分查找是一种在每次比较之后将查找空间一分为二的算法。每次需要查找集合中的索引或元素时，都应该考虑二分查找。如果集合是无序的，我们可以总是在应用二分查找之前先对其进行排序。但要注意排序的成本
target: 要查找的值
index: 查找时的当前位置
left 和 right: 左右指针
mid: 左右指针的中点，用来确定我们应该向左查找还是向右查找的索引
在最简单的形式中，二分查找对具有指定左索引和右索引的连续序列进行操作。这就是所谓的查找空间。二分查找维护查找空间的左、右和中间指示符，并比较查找目标或将查找条件应用于集合的中间值；如果条件不满足或值不相等，则清除目标不可能存在的那一半，并在剩下的一半上继续查找，直到成功为止。如果查以空的一半结束，则无法满足条件，并且无法找到目标。
注意：
（1）二分法搜索可以采用许多替代形式
（2）可能并不总是直接搜索特定值
（3）你不一定能直接缩小一半的查找范围
总之，使用二分法，应该注意数字下标，否则是很容易出错的
|