二分搜索的应用和考察点
二分搜索常见的应用场景
- 在有序序列中查找一个数，整个算法的时间复杂度为O ( l o g N ) O(logN)O(logN)；
- 并不一定非要在有序序列中才能得到应用，只要在二分之后能够淘汰掉一半，这种情况都能够使用二分搜索；
二分搜索考察点一
首先，二分搜索的思想并不是难点，难点在于如何快速地写出正确的代码，尤其是：
对于边界条件的考察以及代码实现的能力；边界条件的重点是，在循环中，因为每次都会被剪一半，如果处理不当会发生死循环，或者漏掉某个数的情况，总之就是一定要仔细设计对中间划分点的逻辑判断，以及设计循环的终止条件，防止出现范围永远不能减小到循环终止的情况。
二分搜索考察点二
二分搜索的第二个考察点是二分搜索的题目变化很多：
- 给定处理或查找的对象不同：比如给定一个无重复值的数组完成某一个具体的功能，和给定一个有重复值的数组完成同样的功能，二者在二分的细节上存在差异；
- 判断条件不同：比如在有序数组中查找等于目标值
target存在的位置，同样可以考察大于等于target存在的位置； - 要求返回的内容不同：比如任意一个等于
target元素的位置，或者等于target最左的位置或者最右的位置，或者是两者的个数等等；
这三种变化可以相互组合衍生出大量的题目。
二分搜索考察点三
在有序循环数组中进行二分搜索：所谓的有序循环数组是指，左边任意长度的数组拿到右边去，右边任意长度的数组拿到左边来。比如数组[1，2，3，4，5]，循环之后可以是[4，5，1，2，3]。
二分搜索的重要提醒：一般我们取得中的位置的常规写法是mid=(left+right)/2，这种写法非常经典，但是当下标值非常大的时候，left+right是可能会产生溢出的。所以更安全的写法是：
布隆过滤器
布隆过滤器可精确(不是准确)的代表一个集合，可精确判断某一元素是否在此集合中，精确程序由用户的具体设计决定。做到100%的精确是不可能的。
布隆过滤器的优势在于：利用很少的空间可以做到精确率较高的程度。
不用额外变量交换两个整数的值
给定整数a和b，想要交换它们的值的常规做法是先申请一个额外的变量，用于保存其中的某个值，之后再进行交换。如果不使用零食变量，使用如下三行代码也可以交换a和b的值：
a = a ^ b; b = a ^ b; a = a ^ b;
不用比较判断，比较大小
给定两个32位整数a和b，返回a和b中较大的。但是不能用任何比较判断。
第一种方法：得到a − b a-ba−b的符号，根据该符号决定返回a或b；
这种方法可能会导致溢出的问题。
第二种做法：
案例三
给定一个整型数组arr，其中只有一个数出现了奇数次，其他人的数都出现了偶数次，请打印这个数。要求时间复杂度为O(N)，额外空间复杂度为O(1)。
任意一个整数n与0异或的结果为n；n与n异或的结果为0。
参考
第六课：二分查找、二叉排序树、位运算的应用
1. 二分查找、二叉排序树的知识要点 2. 数组的二分查找(LeetCode 33,81 Search in Rotated Sorted Array 1,2) 3. 区间二分查找(LeetCode 34. Search for a Range) 4. 排序链表转换为二叉排序树(LeetCode 109. Convert Sorted List to B- Search Tree) 5. 二叉排序树的遍历与改造(LeetCode 538 Convert BST to Greater Tree) 6. 二叉排序树中的第K大的数(LeetCode 230. Kth Smallest Element in a BST) 7. 位运算的知识要点 8. 使用位运算表示集合(LeetCode 78. Subsets) 9. 位运算应用题目(LeetCode 136,137,260. Single Number1,2,3)
