贵阳网站建设哪里好,国内公司排名,松江附近做网站,wordpress在apache2.4算法|数组——二分查找 文章目录 算法|数组——二分查找引言二分查找左闭右闭写法左闭右开写法 总结 引言
首先学习这个算法之前需要了解数组知识#xff1a;数组。
大概介绍以下#xff1a;
数组是存储在连续内存空间上的相同类型数据的集合。数组下标都是从0开始。数组在…算法|数组——二分查找 文章目录 算法|数组——二分查找引言二分查找左闭右闭写法左闭右开写法 总结 引言
首先学习这个算法之前需要了解数组知识数组。
大概介绍以下
数组是存储在连续内存空间上的相同类型数据的集合。数组下标都是从0开始。数组在内存空间的地址都是连续的。
二分查找
首先明确我们的目的找target 左闭右闭写法
思路如下 class Solution{public int search(int[]nums, int target){ int left 0;int right nums.length-1;while(left right){int mid left ((right - left) 1);if (nums[mid] target){return mid;}else if (nums[mid] target){left mid 1;}else if (nums[mid] target){right mid - 1;}}return -1;}
}左闭右开写法
思路如下 class Solution {public int search(int[] nums, int target) {int left 0;int right nums.length;while(left right){int mid left ((right - left) 1);if (nums[mid] target){return mid;}else if (nums[mid] target){left mid 1;}else if (nums[mid] target){right mid;}}return -1;}
}总结 思路如下 明确区间。target的两种情况存在or不存在。对target存在进行讨论 在中间在mid左侧在mid右侧 注意事项 考虑mid定义溢出现象 如果这样子写 int mid (left right) / 2;可能会出现溢出现象。 解决方法如下 int mid left ((right - left) 1);用位移运算符来计算 (right - left) 1这将 right - left 的结果右移一位相当于将其除以 2。相当于 int mid left ((right - left) / 2);考虑区间带来的影响。
