精选留言(305)

• 
  Smallfly

  置顶

  2018-10-27

  有三种方法查找循环有序数组 一、 1. 找到分界下标，分成两个有序数组 2. 判断目标值在哪个有序数据范围内，做二分查找 二、 1. 找到最大值的下标 x; 2. 所有元素下标 +x 偏移，超过数组范围值的取模; 3. 利用偏移后的下标做二分查找； 4. 如果找到目标下标，再作 -x 偏移，就是目标值实际下标。 两种情况最高时耗都在查找分界点上，所以时间复杂度是 O(N）。 复杂度有点高，能否优化呢？ 三、 我们发现循环数组存在一个性质：以数组中间点为分区，会将数组分成一个有序数组和一个循环有序数组。 如果首元素小于 mid，说明前半部分是有序的，后半部分是循环有序数组； 如果首元素大于 mid，说明后半部分是有序的，前半部分是循环有序的数组； 如果目标元素在有序数组范围中，使用二分查找； 如果目标元素在循环有序数组中，设定数组边界后，使用以上方法继续查找。 时间复杂度为 O(logN)。

  展开

  共 41 条评论

  615
• 
  zixuan

  2018-10-31

  思考题对应leetcode 33题，大家可以去练习

  共 4 条评论

  237
• 
  舍得

  2018-10-27

  第一段代码有漏洞，且不说int能不能表示数组的下标问题，毕竟这个数组能越界说明相当庞大了； 主要问题在于，如果我给定的数大于任何一个数组元素，low就会等于n，n是数组越界后的第一个元素，如果它刚好是要查找的值呢？？

  作者回复: 谢谢指正 我稍后改下

  共 7 条评论

  69
• 
  王艳红

  2019-03-05

  王老师，有一个疑惑不太明白 int mid = low + ((high - low)>>1) 这句，为什么要用这种写法呢？我看之前的简单的额二分查找是 int mid = (low + high)/2

  作者回复: 下面的写法有可能会导致溢出，比如low很大，high也很大，之和就溢出了。

  共 14 条评论

  57
• 
  毅仔

  2018-12-23

  第一次见到逻辑这么清晰的二分查找代码，已经被老师俘获了，太优雅了

  

  58
• 
  Geek_86533a

  2019-08-05

  茅塞顿开，刷leetcode的时候，看大神们写的二分查找，找一个数字出现的左右边界，始终无法理解，现在才明白自己陷入了追求代码简洁的误区。感谢老师渡我出苦海！

  共 1 条评论

  51
• 
  John

  2020-05-16

  我来给初学者解释一下IP地址的事吧. 为什么说IP地址可以转化为32位的整数呢? 首先我们看IP地址都是张这样的: "XXX.XXX.XXX.XXX" 一共4段,每段3位(因为你从来没有见过4位的一段的吧). 我们知道2的10次方是1024(程序员记得10月24号这个节日吧), 所有很容易掐指一算得到2^9=512 => 2^8=256. 其实xxx的上限是255, 这是IP地址的规定(反正你也没见过3xx或者4xx的地址吧)!!! 也就是说对于[0, 256)=[0, 255] 这个区间对应的2进制是8位. 刚才说了是4段, 那么就是4*8=32位的2进制喽. 当然了, 我们这段只是论证了对应的2进制是32位而已, 你对这道题的操作倒也不必一定要转化为2进制, 其实也可以干脆把小数点直接抽掉+补上前面的0, 得到一个很大的十进制数字. 这样的后果第一保持顺序的稳定性(其实也没有重复的), 第二很容易从十进制大数转回IP地址. 比如这样 "255.128.16.8 => 255128016008", 最后搜索结束之后再转回去 "255128016008=>255128016008"就可以啦!

  展开

  共 2 条评论

  34
• 
  Victor

  2018-10-27

  今天的IP地址归属地问题，从工程实现的角度考虑，我更偏向于直接使用关系型数据库实现。 也就是将12w条归属地与IP区间的开始、结束存入数据库中。 数据库表ip_table有如下字段：area_name | start_ip | end_ip ，start_ip及end_ip 均建立索引 SQL语句： select area_name from ip_table where input_ip >= start_ip and input_ip <= end_ip; 学习算法的课程常常和自己工程开发的实际结合在一起，感觉两者是相互促进理解的过程。

  展开

  作者回复: 数据库可以 单性能会受限

  共 9 条评论

  30
• 
  charon

  2018-10-26

  用JavaScript实现的最基本的思考题： array是传入的数组，value是要查找的值 思路是通过对比low,high的值来判断value所在的区间，不用多循环一遍找偏移量了~ function search(array,value){ let low = 0; let high = array.length - 1; while(low <= high){ let mid = low + ((high - low) >> 1); if(value == array[low]) return low; if(value == array[high]) return high; if(value == array[mid]) return mid; if(value > array[mid] && value > array[high] && array[mid] < array[low]){ high = mid - 1; }else if(value < array[mid] && value < array[low] && array[mid] < array[low]){ high = mid - 1; }else if(value < array[mid] && value > array[low]){ high = mid - 1; }else{ low = mid + 1; } } return -1 }

  展开

  共 1 条评论

  18
• 
  松鼠鱼

  2020-04-05

  尝试了一下LeetCode的33题，试提供一个Java版本的解法。从提交反馈来看还是不错的： Runtime: 0 ms, faster than 100.00% of Java online submissions for Search in Rotated Sorted Array. public int solution(int[] nums, int target) { int s = 0; int e = nums.length - 1; while (e >= s){ int mid = s + (e-s)/2; if (nums[mid] == target) return mid; if (nums[mid] < nums[e]) { if (target < nums[mid] || target > nums[e]) { e = mid - 1; } else s = mid + 1; } else { if (target < nums[s] || target > nums[mid]) { s = mid + 1; } else e = mid - 1; } } return -1; }

  展开

  共 5 条评论

  17
• 
  姜威

  2018-11-03

  总结：二分查找（下） 一、四种常见的二分查找变形问题 1.查找第一个值等于给定值的元素 2.查找最后一个值等于给定值的元素 3.查找第一个大于等于给定值的元素 4.查找最后一个小于等于给定值的元素 二、适用性分析 1.凡事能用二分查找解决的，绝大部分我们更倾向于用散列表或者二叉查找树，即便二分查找在内存上更节省，但是毕竟内存如此紧缺的情况并不多。 2.求“值等于给定值”的二分查找确实不怎么用到，二分查找更适合用在”近似“查找问题上。比如上面讲几种变体。 三、思考 1.如何快速定位出一个IP地址的归属地？ [202.102.133.0, 202.102.133.255] 山东东营市 [202.102.135.0, 202.102.136.255] 山东烟台 [202.102.156.34, 202.102.157.255] 山东青岛 [202.102.48.0, 202.102.48.255] 江苏宿迁 [202.102.49.15, 202.102.51.251] 江苏泰州 [202.102.56.0, 202.102.56.255] 江苏连云港 假设我们有 12 万条这样的 IP 区间与归属地的对应关系，如何快速定位出一个IP地址的归属地呢？ 2.如果有一个有序循环数组，比如4，5，6，1，2，3。针对这种情况，如何实现一个求“值等于给定值”的二分查找算法？

  展开

  共 4 条评论

  14
• 
  朱坤

  2019-02-25

  置顶的同学的思路一，即先找分界再判断在哪个数组，再二分，其实是可以做到O(Log N)的，找分界的点的规则就是找到首个小于a[0]的元素，思路用老师4个转换问题的解法就可以。按评论做了下leetcode33题，感觉会比较老师给的思考题描述清晰。。因为老师说的找问题，没有明确有几组循环数组。。

  共 3 条评论

  13
• 
  菜鸡程序员

  2018-12-07

  1.如果不知道分界点，找寻分界点没有意义，不如直接遍历。 2.如果知道分界点，查看在哪一边，然后二分法，或者偏移量计算,二分法 老师,我今天这种可以吗: /** * 功能描述:查找第一个大于等于给定值的元素 * * @param null * @return * @author xiongfan * @date 2018/12/7 9:43:00 */ public static int getFirstGreaterValue(int[] array,int value) { int low = 0; int high = array.length - 1; while (low <= high) { int mid = low + (high - low) >> 1; if (array[mid] < value) { low = mid + 1; } else if (array[mid] > value) { high = mid - 1; } else { if (mid == 0 || array[mid - 1] < array[mid]) { return mid; } high = mid - 1; } } return low>array.length-1?-1:low; } /** * 功能描述:查找最后一个小于等于给定值的元素 * * @param null * @return * @author xiongfan * @date 2018/12/7 10:03:00 */ public static int getLastLessValue(int[] array,int value) { int low = 0; int high = array.length - 1; while (low <= high) { int mid = low + (high - low) >> 1; if (array[mid] > value) { high = mid - 1; } else if (array[mid] < value) { low = mid + 1; } else { if (mid > array.length-1 || array[mid] < array[mid + 1]) { return mid; } low = mid + 1; } } return high<0?-1:high; }

  展开

  

  8
• 
  勤劳的小胖子-libo

  2018-10-27

  1. 先二分遍历找到分隔点index，特征是<pre, >=next; 2. 把数组分成二个部分，[0,index-1], [index,length-1]; 3. 分别使用二分查找，找到给定的值。 时间复杂度为2*log(n). 不确定有什么更好的办法。

  共 2 条评论

  8
• 
  疾风狂草

  2018-12-10

  老师，你说二分查找更适合用在“近似”查找问题，在这类问题上，二分查找的优势更加明显。这种问题链式哈希表不是更擅长吗？

  作者回复: 哈希表是精准查找

  

  7
• 
  牛顿的苹果啦

  2019-01-31

  思考题： 可以考虑将数组分为N个有序数组，分别进行二分查找。 代码实现： public int circleBinarySearch(int[] a, int value){ int low = 0, high=0; for(int i=0;i<a.length-1;i++){ //找到有序数组的下标 if(a[i]<a[i+1]){ high=i+1; }else{ //有序数组到顶，二分查找 int i1 = binarySearch(low, high, a, value); if(-1 != i1){ return i1; }else{ low = high+1; } } //high已经到最后一个位置 if(a.length-1 == high){ return binarySearch(low, high, a, value); } } return -1; } private int binarySearch(int low, int high, int[] a, int value){ for(;low<=high;){ int middle = low+((high-low)>>1); if(a[middle] == value){ return middle; } if(a[middle] > value){ high = middle -1; }else{ low = middle +1; } } return -1; }

  展开

  

  5
• 
  狼的诱惑

  2018-10-31

  @老师，请老师或其他高人回复指教 /** * 例如： 4 5 6 1 2 3 * 循环数组的二分查找 总体时间复杂度O(n) */ public static int forEqualsThan(int[] arr, int num) { if (arr[0] == num) { return 0; } int length = arr.length; int low = 0; int high = length - 1; //找到循环节点 for (int i = 0; i < length; i++) { if (i == length - 1) { if (arr[i] > arr[0]) { low = i; high = 0; break; } } else { if (arr[i] > arr[i + 1]) { low = i; high = low + 1; break; } } } //判断第一个节点的大小位置，确定low和high的值，转变为正常有序的二分查找 if (arr[0] < num) { high = low; low = 0; } if (arr[0] > num) { low = high; high = length - 1; } while (low <= high) { int index = low + ((high - low) >> 1); if (arr[index] > num) { high = index - 1; } if (arr[index] < num) { low = index + 1; } if (arr[index] == num) { return index; } } return -1; }

  展开

  共 4 条评论

  5
• 
  低调人生

  2019-05-28

  我觉得查找第一个符合给定的值得那两种写法 第一种更好理解 没看懂作者的写法

  共 3 条评论

  4
• 
  晓杉

  2018-11-16

  老师，我有一个疑问。 使用二分查找的前提是有序数组。 对于本节IP地址问题，我们先进行排序再进行查找，我理解应该时间复杂度是排序平均O(nLogn)再加上二分查找O(logn) 比单纯的顺序遍历O(n)要慢许多了。 是不是实际中，这种无序情况直接使用了顺序遍历查找呢？

  展开

  共 5 条评论

  4
• 
  刘忽悠

  2018-10-26

  第一段代码的想法确实妙，乍眼一看还以为这段代码有问题

  

  4