订阅更新(RSS/Atom): ##　Leetcode 704 二分查找target 这种是在一个元素各不相同的有序数组里面找一个等于target的数解法： 1class Solution 2{ 3public: 4 int search(vector &nums, int target) 5 { 6 int l{0}; 7 int r = nums.size() - 1; 8 int mid; 9 while (l <= r)10 {11 mid = (l + (r - l) / 2);12 if (nums[mid] == target)13 {14 return mid;15 }16 if (target < nums[mid])17 {18 r = mid - 1;19 }20 else21 {22 l = mid + 1;23 }24 }25 return -1;26 }27}; 此时，分三种情况。注意到，在不等于的时候，r和l都对mid有排斥排斥性在二分问题中，mid能不能等于l或者r称为排斥性二分模版常见的二分情景是:对于01数组，找到里面的第一个1出现的位置(重点：这里我们认为1一定会出现，后面的部分会讨论1有可能不出现的情况)00011111这符合自然界的规律，某个实验，在参数小于某个阈值的时候，都是失败的。大于等于这个阈值的时候，都是成功的。这种时候需要我们认真考虑排斥性对于先0后1,一定会出现1的实验，代码为: 1vector v{0, 0, 0, 1, 1, 1}; 2 auto yes = [&](int mid) 3 { return v[mid] == 1; }; 4 size_t l{0}, r{v.size() - 1}; 5 int mid; 6 while (l < r) 7 { 8 mid = l + (r - l) / 2; 9 if (yes(mid))10 r = mid;11 else12 l = mid + 1;13 }14 cout << l; 原因是：我们之所以设置 while(l v{0, 0, 0}; 4 auto yes = [&](int mid) 5 { return v[mid] == 1; }; 6 size_t l{0}, r{v.size() - 1}; 7 int mid; 8 while (l < r) 9 {10 mid = l + (r - l) / 2;11 if (yes(mid))12 r = mid;13 else14 l = mid + 1;15 }16 if (yes(l))17 cout << l;18 else19 cout << -1;20} 确实有效 LOWER_BOUND 和 UPPER_BOUND 对于v={0,1,2,3}lower_bound(v,2)得到2upper_bound(v,2)得到3 对于 1,1,2,2,2,3,3,3l(v,2)=2u(v,2)=5 l(v,1)=0r(v,1)=2 l(v,0)=0r(v,0)=0 l(v,3)=5r(v,3)=6 l(v,4)=6r(v,4)=6 对于1,1,3,3,5,5,7,7 lower_bound(4)=4upper (4) =4 lower_bound:Returns an iterator pointing to the first element in the range [first, last) that is not less than (i.e. greater or equal to) value, or last if no such element is found. upper_bound:Returns an iterator pointing to the first element in the range [first, last) that is greater than value, or last if no such element is found. 区别在于lower_bound是大于等于的第一个upper_bound是大于的第一个 equal_range 返回 pair 第一个指向区域里面第一个等于val的元素，第二个指向区域里面第一个大于val的元素也就是左闭右开的 [,)区间

二分总结