算法－二分查找

二分查找

其实二分查找是一个很简单理解的东西，从他的名字就可以看出，就是要分为两段去查找一个元素

我们确定一个中间元素，然后将这一个元素和左边的部分和右边的部分做对比

然后根据实际情况来选择一个部分来继续做这么一个步骤

直到找到这一个符合标准的元素

举一个最简单的例子

在1 2 3 4 5 6中寻找3这个元素

常规方法就是将整个字符串遍历，然后找到字符3

但是这样的时间复杂度太高了，所以我们可以用二分查找

选择中间值4，发现他大于3，那么他右部分舍去

在找1 2 3的中间值2，发现他小于3，所以左边部分舍去

2 3中选择3，找到元素

这样的时间复杂度是logn，比整个遍历好用

什么时候使用

在我们看到一串数字有二段性（能按照某种规则将这串东西分为两部分）或者找找到什么值但是要求时间复杂度必须是logn的时候，我们就要使用二分查找

模板

在二分查重中，我们常用的模板有两个，我们要谨慎选择和使用，不然会发生死循环

//s[mid]<x,left=mid+1
//s[mid]>=x,right=mid
while(left<right)
{int mid=left（right-left）/2;if(s[mid]<...){left=mid+1;}else{right=mid;}return s[left] or s[right]
}

//s[mid]<=x,left=mid
//s[mid]>x,right=mid-1
while(left<right)
{int mid=left（right-left+1）/2;if(s[mid]>...){right=mid+1;}else{left=mid;}return s[left] or s[right]
}

最后就还是选择模板了，但是不要太过依赖模板，因为题目会改变，我们所能做的就是了解模板的思想，然后根据模板来更改代码