二分查找是干什么的（二分查找和折半查找）

1.概念 如果想要在数组中查找一个数，最基本的方法就是暴力解法：一次遍历，这时候时间复杂度是O(N),二分查找就是其中的一种优化，时间复杂度是O(logN);具体做法是一步一步逼近直到找到。前提是数组需要是一个排序数组。 定义：二分查找也称折半查找（Binary Search），是一种在有序数组中查找某一特定元素的搜索算法。我们可以从定义可知，运用二分搜索的前提是数组必须是有序的，这里需要注意的是，我们的输入不一定是数组，也可以是数组中某一区间的起始位置和终止位置 2.过程 1.二分查找先初始化一个搜索空间，然后再这个搜索空间上去寻找某个值，注意这个搜索空间是有某种规律，比如说是有序的； 2.因为这种规律，直接去看中间值，如果判断中间值和我们想要的结果的关系，比如搜索数字，看中间值和目标值的大小关系； 3.如果mid>t,那证明应该去前半部分搜索；如果mid<t,那说明该去前半部分搜索； 4.然后接着在新的搜索空间执行2，3； 关键 Knuth 大佬（发明 KMP 算法的那位）怎么说的： Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky… 思路很简单，细节是魔鬼； 3.模板 上述功能就是如果能在数组中找到目标值，就返回其索引，如果找不到，就返回其下标；如果目标值比中间值还大，那肯定在中间值右侧(因为数组已经排序好了)，如果目标值比mid值小，那肯定在mid左侧。 细节1：为什么while循环的条件是<=? 因为我们初始化的时候右侧区间是nums.length-1;所以是包括right的，即我们的区间是[left,right],这样一个左闭右闭的区间，把这个区间理解成搜索区间，即我们是在这样一个区间上搜索，那什么时候停止呢，两个原因： 1.找到了目标值，那就停止； 2.没找到目标值，但是搜索区间为空了，没得找了，这时候停止； 所以在最后一个=的时候，比如[2,2]这时候区间还不为空，万一就是这个2呢。 细节2：为什么写成left+((right-left) >> 1); 这主要是为了防止溢出，记住就可以了，注意除以2,用位运算的话会比较快一点，而且记得带外面那个大括号； 细节3： 为什么left = mid + 1，right = mid – 1？ 想一下刚才搜索区间的概念，如果发现了索引mid不是要找的target，那自然要从将mid剔除掉，从mid的左边或者右边找起来了。 缺陷：上述算法存在一个缺陷就是不能返回左右侧边界，比如数组是[1,2,2,2,3], target是2，这时候返回的索引是2，没有办法返回左右边界。 4.样例 34. 在排序数组中查找元素的第一个和最后一个位置 33. 搜索旋转排序数组 剑指 Offer 53 – II. 0～n-1中缺失的数字 仔细体会上面3个样例。 1.解决了上面说到的不能返回左右边界的问题； 2.这个问题是不完全有序数组的二分查找；基本思路就是将其往排序数组上赶，比较mid和left来确定是前半段有序还是后半段有序； 3.是二分查找的一个问题，并不仅仅是查找某个值某个元素，重点去感受最后的left=right=mid；体会最后跳出循环的返回值； 5.体会 当写成这样时：返回的left是第一个>=target的值的索引。 如果原数组有target返回的就是第一个target的索引； 如果没有那就是第一个比target大的值的索引(或者可以理解为要将target插入的位置索引)； 之所以有上面的结论就在于最后一步一定是left=right=mid，而且mid左侧都<t,mid右侧都>=t,这时候执行判断，如果mid大于等于target，那就返回它了，也就是left，如果<target,那就执行left+1，返回的就是第一个>=target的值； 注意查看上面中提到的二分法的模板和细节，注意什么时候带等号，什么时候不带等号； 二分查找本质上就是一个不断缩小搜索空间的过程，比如我们找出某个值，就是在不断的把空间缩小；找出哪个数字乱序，也在不断的把空间缩小；求一个数的开根号，不断的缩小空间然后拿值去逼近。这个过程要多想一下，就是我们不断的缩小空间，然后每次都是拿这个空间上的中间值去做某种判断，然后去逼近我们的结果。 二分查找应用的前提就是一定是一个有序的，或者半有序的，如果是半有序的话原则是就是不断向有序上去赶，因为只有在有序的时候才能去二分； 上面提供的二分查找的模板要始终明白在最后一步跳出循环前两点： 1.最后一步一定是right=left=mid。 2.mid左侧和右侧一定是已经有了规律的了。比如查找值的时候，mid左侧都比t值小，mid右侧都比t值大；比如判断从哪个数字开始乱了，mid左侧一定是整齐的，mid右侧一定是乱的。那这时候只要去判断一下mid的值就可以了。如果mid>t或者说mid乱了，那正好返回left也就是mid，如果mid<t或者说mid没乱，那left=mid+1，这不就正好是第一个大于t或者第一个乱的了吗。 另外，对现在我们的大多数朋友来说还是学编程技术最重要！栽一棵树最好的时间是十年前，其次是现在。对于准备学习编程的小伙伴，如果你想更好地提升你的编程核心能力（内功）不妨从现在开始！ 1.概念 如果想要在数组中查找一个数，最基本的方法就是暴力解法：一次遍历，这时候时间复杂度是O(N),二分查找就是其中的一种优化，时间复杂度是O(logN);具体做法是一步一步逼近直到找到。前提是数组需要是一个排序数组。 定义：二分查找也称折半查找（Binary Search），是一种在有序数组中查找某一特定元素的搜索算法。我们可以从定义可知，运用二分搜索的前提是数组必须是有序的，这里需要注意的是，我们的输入不一定是数组，也可以是数组中某一区间的起始位置和终止位置 2.过程 1.二分查找先初始化一个搜索空间，然后再这个搜索空间上去寻找某个值，注意这个搜索空间是有某种规律，比如说是有序的； 2.因为这种规律，直接去看中间值，如果判断中间值和我们想要的结果的关系，比如搜索数字，看中间值和目标值的大小关系； 3.如果mid>t,那证明应该去前半部分搜索；如果mid<t,那说明该去前半部分搜索； 4.然后接着在新的搜索空间执行2，3； 关键 Knuth 大佬（发明 KMP 算法的那位）怎么说的： Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky… 思路很简单，细节是魔鬼； 3.模板 上述功能就是如果能在数组中找到目标值，就返回其索引，如果找不到，就返回其下标；如果目标值比中间值还大，那肯定在中间值右侧(因为数组已经排序好了)，如果目标值比mid值小，那肯定在mid左侧。 细节1：为什么while循环的条件是<=? 因为我们初始化的时候右侧区间是nums.length-1;所以是包括right的，即我们的区间是[left,right],这样一个左闭右闭的区间，把这个区间理解成搜索区间，即我们是在这样一个区间上搜索，那什么时候停止呢，两个原因： 1.找到了目标值，那就停止； 2.没找到目标值，但是搜索区间为空了，没得找了，这时候停止； 所以在最后一个=的时候，比如[2,2]这时候区间还不为空，万一就是这个2呢。 细节2：为什么写成left+((right-left) >> 1); 这主要是为了防止溢出，记住就可以了，注意除以2,用位运算的话会比较快一点，而且记得带外面那个大括号； 细节3： 为什么left = mid + 1，right = mid – 1？ 想一下刚才搜索区间的概念，如果发现了索引mid不是要找的target，那自然要从将mid剔除掉，从mid的左边或者右边找起来了。 缺陷：上述算法存在一个缺陷就是不能返回左右侧边界，比如数组是[1,2,2,2,3], target是2，这时候返回的索引是2，没有办法返回左右边界。 4.样例 34. 在排序数组中查找元素的第一个和最后一个位置 33. 搜索旋转排序数组 剑指 Offer 53 – II. 0～n-1中缺失的数字 仔细体会上面3个样例。 1.解决了上面说到的不能返回左右边界的问题； 2.这个问题是不完全有序数组的二分查找；基本思路就是将其往排序数组上赶，比较mid和left来确定是前半段有序还是后半段有序； 3.是二分查找的一个问题，并不仅仅是查找某个值某个元素，重点去感受最后的left=right=mid；体会最后跳出循环的返回值； 5.体会 当写成这样时：返回的left是第一个>=target的值的索引。 如果原数组有target返回的就是第一个target的索引； 如果没有那就是第一个比target大的值的索引(或者可以理解为要将target插入的位置索引)； 之所以有上面的结论就在于最后一步一定是left=right=mid，而且mid左侧都<t,mid右侧都>=t,这时候执行判断，如果mid大于等于target，那就返回它了，也就是left，如果<target,那就执行left+1，返回的就是第一个>=target的值； 注意查看上面中提到的二分法的模板和细节，注意什么时候带等号，什么时候不带等号； 二分查找本质上就是一个不断缩小搜索空间的过程，比如我们找出某个值，就是在不断的把空间缩小；找出哪个数字乱序，也在不断的把空间缩小；求一个数的开根号，不断的缩小空间然后拿值去逼近。这个过程要多想一下，就是我们不断的缩小空间，然后每次都是拿这个空间上的中间值去做某种判断，然后去逼近我们的结果。 二分查找应用的前提就是一定是一个有序的，或者半有序的，如果是半有序的话原则是就是不断向有序上去赶，因为只有在有序的时候才能去二分； 上面提供的二分查找的模板要始终明白在最后一步跳出循环前两点： 1.最后一步一定是right=left=mid。 2.mid左侧和右侧一定是已经有了规律的了。比如查找值的时候，mid左侧都比t值小，mid右侧都比t值大；比如判断从哪个数字开始乱了，mid左侧一定是整齐的，mid右侧一定是乱的。那这时候只要去判断一下mid的值就可以了。如果mid>t或者说mid乱了，那正好返回left也就是mid，如果mid<t或者说mid没乱，那left=mid+1，这不就正好是第一个大于t或者第一个乱的了吗。