二分法
二分法
力扣题目连接：二分查找
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
示例一：
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4示例二：
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1提示：
你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间。
思路
二分查找是一个比较简单的算法，其前提条件为：
- 数组内元素是有序的
- 数组中元素不能重复，一旦重复就无法找到唯一下标了
二分查找涉及的很多的边界条件，逻辑比较简单，但就是写不好。例如到底是 while(left < right) 还是 while(left <= right)，到底是right = middle呢，还是要right = middle - 1呢？
写二分法经常写乱，主要是因为对区间的定义没有想清楚，区间的定义就是不变量。要在二分查找的过程中，保持不变量，就是在while寻找中每一次边界的处理都要坚持根据区间的定义来操作，这就是循环不变量规则。
写二分法，区间（接下来要查找的范围）的定义一般为两种，左闭右闭即[left, right]（right也在查找范围内，结果可能是right），或者左闭右开即[left, right)（right不在查找范围内，最终结果不可能是right）。
[left, right]图示以及代码
因为区间为[left, right]，这里要注意：
- while(left<=right)，这里left可以等于right，因为left和right都是查找区间的一部分，所以两者相等说明只有一个查找元素了，这是有意义的。
- if(nums[middle] > target),说明target在middle左边，因为当前这个nums[middle]一定不是target，这时要将查找区间右边界right改为middle-1。if(nums[middle] < target)同理，应当将left改为middle+1.
class Solution {
public:
int search(vector<int>& nums, int target) {
int size = nums.size();
int left = 0;
int right = size-1;
int middle = 0;
while(left<=right)
{
middle = (left + right)/2;
if(nums[middle]>target){
right = middle-1;
}
else if(nums[middle]<target){
left = left+1;
}
else{
return middle;
}
}
return -1;
}
};- 时间复杂度：O(log2 n) 因为二分法每次都查找一半（即1/2）
- 空间复杂度：O(1) 空间复杂度为常数
[left, right）图示以及代码
因为区间为[left, right]，这里要注意：
- while(left < right)，这里left不能等于right，因为right不是查找区间的一部分，所以当left和right相等时说明查找区间内没有数组元素内容了，这没有意义。
- if(nums[middle] > target),说明target在middle左边，因为当前这个nums[middle]一定不是target，而有边界right是取不到的，所以将查找区间右边界right改为middle就可以。但是如果if(nums[middle] < target)，应当将left改为middle+1，因为left仍是查找区间的一部分。
class Solution {
public:
int search(vector<int>& nums, int target) {
int size = nums.size();
int left = 0;
int right = size;
int middle = 0;
while(left<right)
{
middle = (left + right)/2;
if(nums[middle]>target){
right = middle;
}
else if(nums[middle]<target){
left = left+1;
}
else{
return middle;
}
}
return -1;
}
};- 时间复杂度：O(log2 n) 因为二分法每次都查找一半（即1/2）
- 空间复杂度：O(1) 空间复杂度为常数
搜索旋转排序数组
力扣题目连接：搜索旋转排序数组
整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 向左旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 下标 3 上向左旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4
示例 2：
输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1
示例 3：
输入：nums = [1], target = 0
输出：-1
思路
旋转数组，数组内元素是有序的，但旋转了，数组的元素顺序被打乱了。
但是旋转数组的元素是有序的，所以二分查找的思路不变，只是需要考虑旋转数组的边界条件。使用mid二分之后，一侧的数组是有序的，另一侧的数组是无序的。如果target在一侧有序数组内，则继续二分查找，否则将另一侧的数组作为新的查找区间。
代码
class Solution {
public int search(int[] nums, int target) {
int n = nums.length;
// 如果数组为空，则返回-1
if(n == 0){
return -1;
}
// 如果数组只有一个元素，则判断该元素是否等于target
if(n == 1){
return nums[0] == target ? 0 : -1;
}
int l = 0 , r = n - 1;
while (l <= r) {
// 二分查找
int mid = (l+r) / 2;
if(nums[mid] == target){
return mid;
}
// 判断target在哪一侧，为什么这里是<=而不是<？因为<= 可以保证 mid 恰好落在左边界时，仍然正确地认为左区间是有序的，比如数组[3,1]，如果target=1，则mid=0，此时mid恰好落在左边界，但是mid-1会越界，所以这里使用<=。
if (nums[l] <= nums[mid]) {
if(nums[l] <= target && target <= nums[mid]){
r = mid - 1;
}
else{
l = mid + 1;
}
}
else{
if(nums[mid] <= target && target <= nums[r]){
l = mid + 1;
}
else{
r = mid - 1;
}
}
}
return -1;
}
}寻找两个正序数组的中位数
力扣题目连接：寻找两个正序数组的中位数
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。
示例 1：
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2
示例 2：
输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
思路
这个题目最先想到的思路肯定是合并数组然后寻找中位数，但是这个时间复杂度是O(m+n)，不符合题目要求。
看到log(m+n)很自然想到二分查找，但是这个题目的数组是已经排序的，所以二分查找的思路不变，只是需要考虑边界条件。
口述一下思路，如果两个数组A和B长度相加m+n为奇数，则我们要找的便是第(m+n)/2+1大的元素(/是整除，会舍弃小数部分)，如果m+n为偶数，则要找的便是第(m+n)/2大的元素和第(m+n)/2+1大的元素之和除以2。所以本质就是要找这里的第k( (m+n)/2+1或者(m+n)/2 )大的元素。很巧妙那么我们去两个数组都找下标为k/2-1的元素（第k/2个元素），因为两个数组取到的元素个数k/2-1+k/2-1 <= k-2，我们可以比较 A[k/2−1] 和 B[k/2−1]，其中 / 表示整数除法。由于 A[k/2−1] 和 B[k/2−1] 的前面分别有 A[0..k/2−2] 和 B[0..k/2−2]，即 k/2−1 个元素，对于 A[k/2−1] 和 B[k/2−1] 中的较小值，最多只会有 (k/2−1)+(k/2−1)≤k−2 个元素比它小，那么它就不能是第 k 小的数了。
因此我们可以归纳出三种情况：
如果 A[k/2−1]<B[k/2−1]，则比 A[k/2−1] 小的数最多只有 A 的前 k/2−1 个数和 B 的前 k/2−1 个数，即比 A[k/2−1] 小的数最多只有 k−2 个，因此 A[k/2−1] 不可能是第 k 个数，A[0] 到 A[k/2−1] 也都不可能是第 k 个数，可以全部排除。
如果 A[k/2−1]>B[k/2−1]，则可以排除 B[0] 到 B[k/2−1]。
如果 A[k/2−1]=B[k/2−1]，则可以归入第一种情况处理。
这里要注意的是有边界条件，比如有个数组不够长了，那么就是另一个数组当前指向的元素向右移动k-1位指向的元素
比如k==1了，那么要取得值就是现在两个数组所指向元素的较小值
感觉自己解释总是解释不清楚class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int length1 = nums1.length;
int length2 = nums2.length;
int mid = (length1 + length2) / 2;
if((length1 + length2) % 2 == 1){
return (double)getValueOfK(nums1, nums2, mid+1);
}else{
return (double)(getValueOfK(nums1, nums2, mid) + getValueOfK(nums1, nums2, mid+1))/2;
}
}
public int getValueOfK(int[] nums1, int[] nums2, int k){
int length1 = nums1.length;
int length2 = nums2.length;
int index1 = 0;
int index2 = 0;
while(true){
if(index1 == length1){
return nums2[index2 + k - 1];
}
if(index2 == length2){
return nums1[index1 + k - 1];
}
if(k == 1){
return Math.min(nums1[index1],nums2[index2]);
}
int half = k/2;
int newIndex1 = Math.min(index1 + half, length1) - 1;
int newIndex2 = Math.min(index2 + half, length2) - 1;
int pivot1 = nums1[newIndex1];
int pivot2 = nums2[newIndex2];
if(pivot1 <= pivot2){
k -= newIndex1 - index1 + 1;
index1 = newIndex1 + 1;
}else{
k -= newIndex2 - index2 + 1;
index2 = newIndex2 + 1;
}
}
}
}