mid

mid相关知识

• 二分查找排序

  import java.util.Arrays; /** *插入二分排序 * @author 123 * */ public class Sort2{ public static void sort(int[] A){ int[] B = A.clone(); for(int i=1;i<A.length;i++){ int left = 0; int right = i; int mid = 0; while(left<=right){ mid = (left+right)/2; if(A[i]>A[mid]){ left = mid+1; } if(A[i]<A[mid]){ right = mid-1; } if(A[i]==A[mid]){ break; } if(left-right==1&&A[i]>A[mid]){ mid++; } } int j=i; while(
• iOS总结笔记 快速排序 、二分查找的OC实现

  //二分查找 默认查找有序数组 - (NSInteger)searchTarget:(NSInteger)target fromArr:(NSArray *)arr { if (arr.count < 1) { return -1; } NSInteger start,mid,end; start = 0; mid = 0 ; end = arr.count-1; while (start < end-1) {//就剩两个数的时候 start = end - 1;这个条件跳出 mid = start + (end - start)/2; if ([arr[mid] integerValue] > target) { end = mid; }else{ start = mid; } } if (target == [arr[start]
• iOS OC实现二分查找和快速排序

  //二分查找 默认查找有序数组 - (NSInteger)searchTarget:(NSInteger)target fromArr:(NSArray *)arr { if (arr.count < 1) { return -1; } NSInteger start,mid,end; start = 0; mid = 0 ; end = arr.count-1; while (start < end-1) {//就剩两个数的时候 start = end - 1;这个条件跳出 mid = start + (end - start)/2; if ([arr[mid] integerValue] > target) { end = mid; }else{ start = mid; } } if (target == [arr[start]
• 二分法查找

  # 二分查找(折半查找)title: 二分查找tags: 数据结构与算法之美author: 辰砂一、简介二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列 （解释：所以二分查找的时候一定要是有序的数组）二、过程若k==R[mid].key，查找成功 若k<R[mid].key，则high=mid-1若k>R[mid].key，则low=mid+11.查找 212.查找70三、算法描述1.非递归设表长为n，low、high和mid分别指向待查元素所在区间的上界、下界和中点,k为给定值初始时，令low=1,high=n,mid=(low+high)/2让k与mid指向的记录比较若k==R[mid].key，查找成功若k<R[mid].key，则high=mid-1若k>R[mid].key，则low=mid+1重复上述操作，直至low>high时，查找失败int Sea

mid相关课程

• 人人都能学会数据分析 零基础入门，人人都能学会；产品、运营、程序员通用版

  进阶 846人正在学习

• Java设计模式精讲-Debug方式+内存分析，真正学懂设计模式 系统学习设计原则，设计模式，锤炼编码内功，赢取高薪Offer

  中级 2932人正在学习

• Elastic-job + Quartz精讲 实现企业级定时任务 经典电商案例，快速入门+框架整合+Java高级玩法+定时任务实现。

  中级 299人正在学习

mid相关教程

• 1.3 具体实现代码(递归实现) fun main() { val numberArray = intArrayOf(1, 3, 5, 7, 9, 11) println(binarySearch(numberArray, 0, numberArray.size - 1, 5))}fun binarySearch(numberArray: IntArray, low: Int, high: Int, targetNum: Int): Int { if (low > high) { return -1 } val mid = (low + high) ushr 1 if (targetNum == numberArray[mid]) { return mid } return if (targetNum > numberArray[mid]) { binarySearch(numberArray, mid + 1, high, targetNum) } else { binarySearch(numberArray, low, mid - 1, targetNum) }}
• 3.2 求解思路详解 首先，我们将 3.1 节中的求解思路用下图表示：如图，我们可以更清楚地明白求解一个数组的最大子数组问题就是对 3.1 节中的步骤 2 中的三种情况的分别求解， 步骤 2 中的情况 a 和情况 b 可以通过递归求解得出结果，所以我们现在先看一下情况 c 的具体求解过程。情况 c 的求解很容易在线性时间内就可以得出结果，他并不是原问题的一个规模更小的实例，因为情况 c 中加入了一个限制（求出的子数组必须跨越下标为 mid 的中间节点）。如上图的右边图形所示，情况 c 的求解结果都会有两个子数组 A [i,mid] 和 A [mid+1,j] 组成，其中 low <= i <= mid <= j <=high。因此，我们只需要找出形如 A [i,mid] 和 A [mid+1,j] 的最大子数组，然后将其合并即可。我们用下面的伪代码 FindMaxCrossSubarray 描述 3.1 节中 步骤 2 中的情况 c 具体实现过程：FindMaxCrossSubarray(A, low, mid ,high): leftSum = minInteger; //设置左边的最大连续和初始值为最小整数值 sum =0; maxLeft = mid; //记录左边最大子数组的下标位置,初始化为mid for (i=mid; i>=low; i--){ sum = sum + A[i]; if (sum > leftSum){ leftSum = sum; maxtLeft = i; } } rightSum = minInteger; //设置右边的最大连续和初始值为最小整数值 sum = 0; maxtRight = mid + 1; //记录右边最大子数组的下标位置,初始化为mid+1 for (j=mid+1; j<=low; j++){ sum = sum + A[j]; if (sum > rightSum){ rightSum = sum; maxtRight = j;//记录左边最大子数组的下标位置 } } //返回结果是一个三元组数据，分别是最大子数组的开始下标，结束下标，求和的值 return (maxLeft,maxRight,leftSum+rightSum); 上述伪代码的描述中的第 2 至第 11 行，是求解左半部分 A [low,mid] 的最大子数组的过程，因为必须包含下标为 mid 的元素，所以从下标为 mid 的中间节点开始逐步递减到下标为 low 的元素，对应伪代码中的第 5 至第 11 行的 for 循环结构，循环的过程中会记录下左边部分的最大子数组的具体值及左半部分的下标位置。同理，上述伪代码的第 12 至第 21 行对应的是求解右半部分 A [mid+1,high] 的最大子数组的过程。最后，伪代码中的第 23 行综合左右两边求解结果，返回必须跨越下标为 mid 的中间元素时，对应的原数组 A 的最大子数组结果。当我们可以清楚地知道步骤 2 中的情况 c 的求解过程时，我们就可以综合知道对于数组 A 求解最大子数组的整体过程，用伪代码 FindMaxSubarray 描述如下：FindMaxSubarray(A,low,high): if (high == low){ return new Result(low,high,A[low]); //基础情况，只有一个元素时候的处理情况 }else { //对应2.1节中步骤1，找到中间元素 int mid = (low + high)/2; //对应2.1节中步骤2，分别对应a,b,c三种情况求解最大子数组结果 (leftLow,leftHigh,leftSum) = FindMaxSubarray(A,low,mid); (rightLow,rightHigh,rightSum) = FindMaxSubarray(A,mid+1,high); (crossLow,crossHigh,crossSum) = FindMaxCrossSubarray(A,low,mid,high); //对应2.1节中步骤3，比较得出最后结果 if(leftSum >= righSum && leftSum >= crossSum){ return (leftLow,leftHigh,leftSum); }else if (rightSum >= leftSum && rightSum >= crossSum){ return (rightLow,rightHigh,rightSum); }else { return (crossLow,crossHigh,crossSum); } }上述求解数组 A 的最大子数组的整体过程伪代码，主要就是由我们在 2.1 节中描述的三大步骤而来。代码第 2 至第 4 行，主要表明了最基础的情况的处理方式。代码第 4 至第 18 行对应着具体的实现方式，第 8 行和第 9 行分别是对子问题的递归求解，第 10 行调用 FindMaxCrossSubarray 过程，求解跨越中间节点的最大子数组求解方式，最后第 12 至 18 行对比三种情况的结果得出最终结果。
• 1.2 具体实现代码(递推实现) fun main() { println(binarySearch(intArrayOf(1, 3, 5, 7, 9, 11), 5))}fun binarySearch(numberArray: IntArray, targetNum: Int): Int { var low = 0 var high = numberArray.size - 1 while (low <= high) { var mid = (low + high) ushr 1// ushr表示Kotlin中的中缀调用函数相当于Java中无符号右移位运算符>>> when { targetNum == numberArray[mid] -> return mid targetNum > numberArray[mid] -> low = mid + 1 else -> high = mid - 1 } } return -1}
• 1. 连续数列 首先看题目，这是 leetcode 中的面试题部分，题目内容如下：给定一个整数数组，找出总和最大的连续数列，并返回总和。示例：输入： [-2,1,-3,4,-1,2,1,-5,4]输出： 6解释： 连续子数组 [4,-1,2,1] 的和最大，为 6。进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。这个很明显是一道动态规划问题，而且使用动态规划方法的时间复杂度为 O(n)O(n)O(n)，空间复杂度可以优化为 O(1)O(1)O(1)。题目描述中已经说明了可以使用分治法去求解该问题。那我们就要思考，如何分解问题，如何合并子问题的解。首先定义解决该问题的方法：def divide(nums, left, right): """ 返回nums[left:right+1]总和最大的连续数列 """ pass分解终止条件当数组为空时，我们就可以停止分解了，转而合并结果：if left == right: return nums[left]分解问题每次将序列对半分割即可，然后使用递归得到子问题的解：# 中间一分为二mid = (left + right) // 2# 递归法：得到左边最大子序列和，不包含右边序列leftSum = divide(nums, left, mid)# 递归得到右边最大子序列和，不包含mid及其左边序列rightSum = divide(nums, mid + 1, right)合并子问题的解这是最关键的一步，上面把序列规模进行对半分割后，我们需要通过左边序列的解和右边序列的解一起来得出最终的完整序列的解。假设我们定义方法： divide(nums, left, right) 为序列 nums[left:right+1] 中最大连续子列的和；进行规模分割，有 mid=(left + right) // 2，那么原来的列表被划分为两个子列表：nums[left, mid+1] 和 nums[mid+1, right]。此时 divide(nums, left, mid) 结果表示列表 nums[left:mid+1] 中的最大子序列和，记为 leftSum，而 divide(nums, mid+1, right) 的结果表示的是 nums[mid+1:right] 中的最大子序列和，记为 rightSum。那么我们仅拿着左右着两边最大子序列和的最大值，即 max(leftSum, rightSum) 来作为原问题的解，是否可行？显然是不行的，因为如果原问题的最大连续子列并不单独在左边和右边，而可能同时包含左子列和右子列的元素：分治解法思路此时，我们需要考虑如何从左右子序列中找到包含左右子序列元素的最大连续子序列和。因为序列连续，所有会比较简单，我们直接从 mid 开始分别往左边移动，计算包含每个元素的连续和 (该元素到 mid 位置的元素全部要包括)，找到最大值，得到 leftMidSum。右边的子序列做同样的操作，得到 rightMidSum。最后这两个值的和就是同时包含左右子序列元素的最大连续数列的和：leftMidSum + rightMidSum。这个时候我们在拿这三个的值进行比较，找到最大值，此时得到的结果才是原问题的解：max(max(leftSum, rightSum), leftMidSum + rightMidSum)。寻找包含左右子列元素的最大连续数列和上述实现查找包含左右连续子序列最大和的方法如下：# 从找出包含mid的左边连续序列的最大值leftVal = 0 leftMidSum = nums[mid] - 1for i in range(mid, left - 1, -1): leftVal += nums[i] leftMidSum = max(leftVal, leftMidSum) # 找出右边序列中最大值rightVal = 0 rightMidSum = nums[mid + 1] - 1for i in range(mid + 1, right + 1): rightVal += nums[i] rightMidSum = max(rightVal, rightMidSum)最后原问题的解为三个值中的最大值，即：max(max(leftSum, rightSum), leftMidSum + rightMidSum)通过上述分析，我们最终得到如下 Python 代码：def maxSubArray(nums): """ 分治法 """ def divide(nums, left, right): if left == right: return nums[left] # 中间一分为二 mid = (left + right) // 2 # 递归法：得到左边最大子序列和，不包含右边序列 leftSum = divide(nums, left, mid) # 递归得到右边最大子序列和，不包含mid及其左边序列 rightSum = divide(nums, mid + 1, right) # 从找出包含mid的左边连续序列的最大值 leftVal = 0 leftMidSum = nums[mid] - 1 for i in range(mid, left - 1, -1): leftVal += nums[i] leftMidSum = max(leftVal, leftMidSum) # 找出右边序列中最大值 rightVal = 0 rightMidSum = nums[mid + 1] - 1 for i in range(mid + 1, right + 1): rightVal += nums[i] rightMidSum = max(rightVal, rightMidSum) # 此时leftMidSum + rightMidSum便是中间包含mid的连续子序列的最大值 return max(max(leftSum, rightSum), leftMidSum + rightMidSum) return divide(nums, 0, len(nums) - 1) 这个执行的时间复杂度为 O(nlogn)O(nlogn)O(nlogn)，提交代码耗时在所有 Python3 提交中垫底，但是这个解题的思路却是很重要的，锻炼我们分治求解能力。
• 3.1 分治算法求解思路 在这里，我们用分治算法求解最大子数组问题，主要思路如下：步骤 1：找到数组 A 的中间元素，其下标记为 mid，根据分治策略，将数组 A [low,high] 根据中间元素划分为 A [low,mid]， A [mid+1,high] 两个部分；步骤 2：假设数组 A 的最大子数组为 A [i, j]，那么 A [i, j] 只有以下三种可能：a: 最大子数组 A [i, j] 完全位于 A [low, mid] 中，此时有 low <= i <= j <= mid;b: 最大子数组 A [i, j] 完全位于 A [mid+1, high] 中，此时有 mid+1 <= i <= j <= high;c: 最大子数组 A [i, j] 跨域了中间元素，则 low <= i <= mid <= j <= high。分别计算上述三种对应的最大子数组的结果；Tips: 在这里，情况 a 和情况 b 这两种情况所得的子问题和之前求解数组 A 的最大子数组的问题形式完全一样，这里是分治思想的主要体现，将大的问题拆分成了两个相同形式的小问题；情况 c 这时候可以直接求解，在 3.2 节中会具体介绍其求解过程。步骤 3对步骤 2 三种情况的求解结果进行比较，其中最大子数组的结果为最大值的情况就是我们的所求结果。
• 4.JAVA 代码实现 在说明求解最大子数组的整个过程之后，接下来，我们看看如何用 java 代码实现最大子数组问题的求解。package divide_and_conquer;public class MaxSubarray { //内部类，用来存储最大子数组的返回结果， private static class Result { int low; int high; int sum; public Result(int low, int high, int sum) { this.low = low; this.high = high; this.sum = sum; } @Override public String toString() { return "Result{" + "low=" + low + ", high=" + high + ", sum=" + sum + '}'; } } private static Result FindMaxCrossSubarray(int[]A,int low, int mid, int high){ //寻找左边的连续最大值及记录位置 int leftSum = Integer.MIN_VALUE; int sum = 0; int maxLeft = mid; for (int i=mid; i>=low; i--){ sum = sum + A[i]; if(sum > leftSum){ leftSum = sum; maxLeft = i; } } //寻找右边的连续最大值及记录位置 int rightSum = Integer.MIN_VALUE; int maxRight = mid+1; sum = 0; for ( int j=mid+1; j<=high;j++){ sum = sum + A[j]; if(sum > rightSum){ rightSum = sum; maxRight = j; } } //返回跨越中间值的最大子数组结果 return new Result(maxLeft,maxRight,leftSum + rightSum); } public static Result FindMaxSubarray(int[] A, int low, int high){ //数组只有一个元素时的处理情况 if (high == low){ return new Result(low,high,A[low]); }else { //对应思路中步骤1，找到中间元素 int mid = (low + high)/2; //对应思路中步骤2，分别对应a,b,c三种情况求解最大子数组结果 Result leftResult = FindMaxSubarray(A,low,mid); Result rightResult = FindMaxSubarray(A,mid+1,high); Result crossResult = FindMaxCrossSubarray(A,low,mid,high); //对应步骤3，比较 if(leftResult.sum >= rightResult.sum && leftResult.sum >= crossResult.sum){ return leftResult; }else if (rightResult.sum >= leftResult.sum && rightResult.sum >= crossResult.sum){ return rightResult; }else { return crossResult; } } } public static void main(String[] args){ int[] A = {12, -3, -16, 20, -19, -3, 18, 20, -7, 12, -9, 7, -10}; System.out.println(FindMaxSubarray(A,0,A.length-1).toString()); }}运行结果如下：Result{low=6, high=9, sum=43}运行结果中的 low 表示最大子数组在数组 A 中的开始下标，high 表示最大子数组在数组 A 中的终止下标，sum 表示最大子数组的求和值，对应到我们的实例数组 A 中，对应的最大最大子数组为 [18,20,-7,12]。代码中第 5 行至 25 行的 Result 内部类，主要是用来存储最大子数组的返回结果，定义了子数组的开始下标，结束下标，求和值。代码的第 27 至 55 行是最大子数组跨越中间节点时候的最大子数组求解过程。代码的第 58 至 78 行是整个最大子数组的求解过程。代码的第 81 行和 82 行是求解最大子数组过程的一个示例，输出最大子数组的求解结果。

mid相关搜索

mac osx machine_start macox magellan malloc manifest manifest文件 map map 遍历 mapreduce编程 maps google com margin margin bottom margin left margin right margin top marginbottom marginheight marginleft margintop

查看更多慕课网实用课程