【算法编程】整数二分法

【算法编程】整数二分法

问题描述&＃xff1a;
  整数二分法是常用的二分搜索算法&＃xff0c;其主要应用场景是&＃xff1a;

给定一个有序且存在重复元素的序列&＃xff0c;要求找出某个元素的起始位置和终点位置

  例如给定一个序列 1,2,4,4,4,4,7,7,9&＃xff0c;则元素4的起始位置是2&＃xff0c;终点位置是5&＃xff1b;元素7的起始位置是6&＃xff0c;终点位置是7。

分析&＃xff1a;
  给定包含 $n$ 序列 a 需要实现两个二分函数&＃xff0c;分别寻找待查询的元素 $m$ 的最起始位置和最末尾的位置&＃xff0c; 若不存在则返回 -1。

• 起始位置&＃xff08;左侧&＃xff09;&＃xff1a;
  取区间 $[l,r]$ 的中心位置&＃xff0c;记做 $mid\&＃61;(l\&＃43;r)/2$&＃xff0c; 如果当 $a[mid]>\&＃61;m$&＃xff0c;则待查询的元素 $m$ 的最左侧一定是在区间 $[l,mid]$。因此其可以查询起始位置。同理&＃xff0c;当 $a[mid]<m$&＃xff0c;则待查元素不可能出现在 $[l,mid]$&＃xff0c; 只可能在 $[mid\&＃43;1,r]$。

当 $a[mid]>\&＃61;m$ 时&＃xff0c;只能保证 $m$ 的最起始位置在区间 $[l,mid]$&＃xff0c; 而最右侧位置是有可能比 $mid$ 大的&＃xff0c;例如上图序列 1,2,4,4,4,4,7,7,9&＃xff0c;$mid\&＃61;4$&＃xff0c;可以找到最左侧的位置2一定在子区间 $[0,4]$。

• 末尾位置&＃xff08;右侧&＃xff09;
  取区间 $[l,r]$ 的中心位置&＃xff0c;记做 $mid\&＃61;(l\&＃43;r\&＃43;1)/2$&＃xff0c;如果 $a[mid]<\&＃61;m$&＃xff0c;则待查元素的 $m$ 的最右侧端点一定在区间 $[mid,r]$。 例如序列 1,2,4,4,4,4,7,7,9&＃xff0c;$mid\&＃61;4$&＃xff0c; 4的最右侧位置是5&＃xff0c;即一定在 $[4,7]$ 区间。反之&＃xff0c;如果 $a[mid]>\&＃61;m$&＃xff0c;则待查元素一定不可能在 $[mid,r]$&＃xff0c; 而在 $[l,mid-1]$。

算法实现&＃xff1a;

#include
#include
using namespace std;// 当中间值小于等于目标值时&＃xff0c;则答案一定在右侧区间&＃xff0c;包含中间值。此时可以获取最右侧端点
int b_search1(vector<int> a, int l, int r, int m) {while(l < r) {int mid &＃61; l &＃43; r &＃43; 1 >> 1;if(a[mid] <&＃61; m) {l &＃61; mid;}else {r &＃61; mid - 1;}}if(a[l] &＃61;&＃61; m) return l;else return -1;
}// 当中间值大于等于目标值时&＃xff0c;则答案一定在左侧区间&＃xff0c;包含中间值&＃xff0c;此时获得最左侧端点
int b_search2(vector<int> a, int l, int r, int m) {while(l < r) {int mid &＃61; l &＃43; r >> 1;if(a[mid] >&＃61; m) {r &＃61; mid;}else {l &＃61; mid &＃43; 1;}}if(a[l] &＃61;&＃61; m) return l;else return -1;
}int main(){int n, q, m, p;vector<int> a;scanf("%d%d", &n, &q);for(int i&＃61;0; i<n; i&＃43;&＃43;) scanf("%d", &p), a.push_back(p);for(int i&＃61;0; i<q; i&＃43;&＃43;) {scanf("%d", &m);int left &＃61; -1, right &＃61; -1;left &＃61; b_search2(a, 0, n - 1, m);if(left !&＃61; -1) right &＃61; b_search1(a, 0, n - 1, m);cout<<left<<&＃39; &＃39;<<right<<endl;}return 0;
}