好看简单易做的网站,wordpress 格式,兰溪自适应网站建设特点,温州论坛招聘目录
一、概念
二、思路
三、边界问题 一、概念
在一本书中查找某一页#xff0c;我们总是倾向于先翻到整本书的中间#xff0c;然后根据当前页数判断我们想要找的页在当前页的左半本中还是右半本中#xff0c;接着继续翻到剩下半本书的中间......
这就是二分查找思想在…目录
一、概念
二、思路
三、边界问题 一、概念
在一本书中查找某一页我们总是倾向于先翻到整本书的中间然后根据当前页数判断我们想要找的页在当前页的左半本中还是右半本中接着继续翻到剩下半本书的中间......
这就是二分查找思想在现实中的应用但为什么这种方法能够比较快的查找到我们想要的页数这是因为书中的页数是有序的通过当前页数与目标页数的比较我们能够确保目标页在当前页的左侧还是右侧 二、思路
二分查找的时间复杂度为O(logN)但是只适用于在有二分性质的序列中进行查找 二分性质即我们可以自定义一个性质让区间的左半部分都不满足右半部分都满足 最朴素的场景有序的数组
以下面的有序数组为例首先用l和r维护我们需要二分的区间 取区间的中点判断中点值与我们的目标的大小关系 注意如果区间元素的个数是奇数那么只有一个中点但如果元素个数是偶数那么就会存在两个中点例如上面的5和7都是中点 此处我们只讨论比较特殊的情况即有偶数个元素的情况
对于该情况我们可以选择每次取区间的左中点或右中点
取左中点
int mid (l r) / 2;
int mid l (r - l) / 2; //防溢出
如果采用上面(l r) / 2的方式来取左中点如果l和r的值过大则有数值溢出的风险因此建议使用第二个的方式
取右中点
int mid (l r 1) / 2;
int mid l (r - l 1) / 2; //防溢出
由于除法向下取整因此如果元素个数为奇数不论是以取左中点的方式还是取右中点的方式我们都能够取到中点例如 下面以偶数个元素为例
以取左中点为例我们取左中点值5 5比8小且我们的数组是升序的则要查找的目标在右半部分 重复上述步骤
要理解二分查找的思路并不难有难度的地方在于其边界问题的处理 三、边界问题
以取左中点为例我们先来看正确的代码
int Binary_Search(int* a, int sz, int x) //假设数组升序
{int l 0, r sz - 1; //区间左右边界while(l r){int mid l (r - l) / 2; //取左中点if(a[mid] x) //中点值比x大目标在左半部分r mid;else if(a[mid] x) //中点值比x小目标在右半部分l mid 1; else //相等return mid; //返回下标}//走出循环说明lr判断此时位置是否与x相等if(a[l] x)return l;return -1;
}
可以看到当中点值比x大时目标在左半部分r移动到原来mid的位置但当中点值比x小时目标在右半部分而l却移动到了mid1的位置。为什么不是和r一样移动到mid
我们看一个最简单的例子 只有两个元素中点mid与l位置重合且目标为2大于中点值1此时l需要移动到mid1的位置 可以正常找到我们的目标
但如果上一步中l移动到mid的位置会怎么样呢l和mid的位置本来就是重合的移动过后位置没有改变导致死循环
这说明不论是取左中点还是右中点一旦边界问题没有处理好那么就会导致死循环
取右中点的代码
int Binary_Search(int* a, int sz, int x) //假设数组升序
{int l 0, r sz - 1; //区间左右边界while(l r){int mid l (r - l 1) / 2; //取右中点if(a[mid] x) //中点值比x大目标在左半部分r mid - 1;else if(a[mid] x) //中点值比x小目标在右半部分l mid; else //相等return mid; //返回下标}//走出循环说明lr判断此时位置是否与x相等if(a[l] x)return l;return -1;
}
修改对应取中点的方式并修改r和l的移动方式即可原理和上面是相同的
如果不想考虑边界情况则还有一种方式
int Binary_Search(int* a, int sz, int x) //假设数组升序
{int l 0, r sz - 1; //区间左右边界while(l r){int mid l (r - l) / 2; //取左中点//int mid l (r - l 1) / 2; //取右中点if(a[mid] x) //中点值比x大目标在左半部分r mid - 1;else if(a[mid] x) //中点值比x小目标在右半部分l mid 1; else //相等return mid; //返回下标}return -1;
}
在这种方式下r和l移动后都不会与原来的mid位置重合
完.
