算法——二分法

根本先容

二分法是 每次都清除半个区间，然后在剩余的半个区间内探求解 的方法，清除半个区间的条件是：区间是有序的，如许一来，当解 小于 区间中点时，就可以在 左子区间 探求；当解 大于 区间中点时，就可以在 右子区间 探求。当解 便是 区间中点时，根据要求在子区间探求或返回。
实现

二分法有两种实现：一种是找 前驱，一种是找 后继。在办理现实标题时须要根据标题标要求差别来采取差别的实现。
后继

界说

在单调递增序列中找                               x                          x               x 或                               x                          x               x 的后继 的界说：在单调递增序列 a 中，假如有                               x                          x               x，则找第一个                               x                          x               x 的位置；假如没有                               x                          x               x，则找比                               x                          x               x 大的 第一个数 的位置。
举例

比方对于 a = [1, 2, 4, 4, 6]，假如要找                               4                          4               4 或                               4                          4               4 的后继，则返回 第一个                              4                          4               4 的索引 2；假如要找                               3                          3               3 或                               3                          3               3 的后继，则返回比                               3                          3               3 大的 第一个数（即第一个                              4                          4               4）的索引 2。
代码

1. int binarySearch(int[] nums, int target) {
2.     int left = 0, right = nums.length - 1; // left, right 分别是区间的左端点和右端点
3.     while (left < right) {
4.         int mid = left + (right - left >> 1);
5.         if (target <= nums[mid]) { // 如果目标值小于或等于区间中点
6.             right = mid; // 则在左子区间查找
7.         } else { // 如果目标值大于区间中点
8.             left = mid + 1; // 则在右子区间查找
9.         }
10.     }
11.     return left; // 返回 第一个target的位置 或 第一个比target大的元素的位置
12. }

复制代码

前驱

界说

在单调递增序列中找                               x                          x               x 或                               x                          x               x 的前驱 的界说：在单调递增序列 a 中，假如有                               x                          x               x，则找末了一个                               x                          x               x 的位置；假如没有                               x                          x               x，则找比                               x                          x               x 小的 末了一个数 的位置。
举例

比方对于 a = [1, 2, 4, 4, 6]，假如要找                               4                          4               4 或                               4                          4               4 的前驱，则返回 末了一个                              4                          4               4 的索引 3；假如要找                               5                          5               5 或                               5                          5               5 的前驱，则返回比                               5                          5               5 小的 末了一个数（即末了一个                              4                          4               4）的索引 3。
代码

1. int binarySearch(int[] nums, int target) {
2.     int left = 0, right = nums.length - 1; // left, right 分别是区间的左端点和右端点
3.     while (left < right) {
4.         int mid = left + (right - left + 1 >> 1);
5.         if (target < nums[mid]) { // 如果目标值小于区间中点
6.             right = mid - 1; // 则在左子区间查找
7.         } else { // 如果目标值大于或等于区间中点
8.             left = mid; // 则在右子区间查找
9.         }
10.     }
11.     return left; // 返回 最后一个target的位置 或 最后一个比target小的元素的位置
12. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！qidao123.com:ToB企服之家，中国第一个企服评测及软件市场,开放入驻,技术点评得现金