leetcode 之 二分查找（java）（5）
9. 167、两数之和Ⅱ-输入有序数组
题目描述 ：
给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。
以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。
你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。
你所设计的解决方案必须只使用常量级的额外空间。
示例 1：
输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
示例 2：
输入：numbers = [2,3,4], target = 6
输出：[1,3]
解释：2 与 4 之和等于目标数 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3] 。
示例 3：
输入：numbers = [-1,0], target = -1
输出：[1,2]
解释：-1 与 0 之和等于目标数 -1 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
提示：
2 <= numbers.length <= 3 * 104-1000 <= numbers[i] <= 1000numbers按 非递减顺序 排列-1000 <= target <= 1000- 仅存在一个有效答案
题解 ：
- 该题目符合二分的两个条件
-
- 数组有序
- 所求答案单一
时间复杂度 O（n logn）
遍历数组每一个下标的数字，然后，l = i + 1, r = n - 1。
使用二分对[ l, r ] 区域求出结果是 target - nums[i]的值，最后返回 [ i + 1, mid + 1 ]即为正确结果。
代码 ：
public int[] twoSum(int[] numbers, int target) {
int n = numbers.length;
for(int i = 0; i < n; i ++ ) {
int l = i + 1, r = n - 1;
int tem = target;
tem -= numbers[i];
while(l <= r) {
int mid = (l + r) / 2;
if(numbers[mid] > tem) r = mid - 1;
else if(numbers[mid] < tem) l = mid + 1;
else return new int[]{i + 1, mid + 1};
}
}
return null;
}
10. 153、寻找旋转排序数组中的最小值
题目描述 ：
已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
- 若旋转
4次，则可以得到[4,5,6,7,0,1,2] - 若旋转
7次，则可以得到[0,1,2,4,5,6,7]
注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。
示例 2：
输入：nums = [4,5,6,7,0,1,2]
输出：0
解释：原数组为 [0,1,2,4,5,6,7] ，旋转 3 次得到输入数组。
示例 3：
输入：nums = [11,13,15,17]
输出：11
解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。
提示：
n == nums.length1 <= n <= 5000-5000 <= nums[i] <= 5000nums中的所有整数 互不相同nums原来是一个升序排序的数组，并进行了1至n次旋转
题解 ：
本题目的话，还是使用二分，但是首先要明确二分的条件，
这道题，它有一个性质，每次旋转之后，分为两个有序区间，同时左边区间的所有数一定比第二个区间的最后一个数要大，同时右边区间是一个递增数组，因此，我们可以很明显的，单独取出来num[n - 1]这个数，然后对剩下的区间使用二分进行求。
- 它们满足具有单一的性质，即 （比nums[n - 1] 大/小）
我们使用闭区间方法求解，即 [0, n - 2]的区间内求解。
代码 ：
public int findMin(int[] nums) {
int n = nums.length;
int l = 0, r = n - 2;
if(nums[n - 1] > nums[0]) return nums[0];
while(l <= r) {
int mid = l + (r - l) / 2;
if(nums[mid] > nums[n - 1]) l = mid + 1;
else if(nums[mid] < nums[n - 1]) r = mid - 1;
}
return nums[l];
}
原文地址：https://blog.csdn.net/su_xu_chao/article/details/144260183
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！