Smallfly 置顶2018-10-27有三种方法查找循环有序数组
一、
1. 找到分界下标，分成两个有序数组
2. 判断目标值在哪个有序数据范围内，做二分查找
二、
1. 找到最大值的下标 x;
2. 所有元素下标 +x 偏移，超过数组范围值的取模;
3. 利用偏移后的下标做二分查找；
4. 如果找到目标下标，再作 -x 偏移，就是目标值实际下标。
两种情况最高时耗都在查找分界点上，所以时间复杂度是 O(N）。
复杂度有点高，能否优化呢？
三、
我们发现循环数组存在一个性质：以数组中间点为分区，会将数组分成一个有序数组和一个循环有序数组。
如果首元素小于 mid，说明前半部分是有序的，后半部分是循环有序数组；
如果首元素大于 mid，说明后半部分是有序的，前半部分是循环有序的数组；
如果目标元素在有序数组范围中，使用二分查找；
如果目标元素在循环有序数组中，设定数组边界后，使用以上方法继续查找。
时间复杂度为 O(logN)。展开 10 291
2018-10-31思考题对应leetcode 33题，大家可以去练习 1 103
2018-10-27第一段代码有漏洞，且不说int能不能表示数组的下标问题，毕竟这个数组能越界说明相当庞大了；
主要问题在于，如果我给定的数大于任何一个数组元素，low就会等于n，n是数组越界后的第一个元素，如果它刚好是要查找的值呢？？作者回复: 谢谢指正 我稍后改下
3 31
2019-03-05王老师，有一个疑惑不太明白
int mid = low + ((high - low)>>1)
这句，为什么要用这种写法呢？我看之前的简单的额二分查找是
int mid = (low + high)/2作者回复: 下面的写法有可能会导致溢出，比如low很大，high也很大，之和就溢出了。
3 23
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;
学习算法的课程常常和自己工程开发的实际结合在一起，感觉两者是相互促进理解的过程。展开作者回复: 数据库可以 单性能会受限
1 15
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
}展开 13
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。针对这种情况，如何实现一个求“值等于给定值”的二分查找算法？展开 3 8
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;
}展开 7
2019-02-25置顶的同学的思路一，即先找分界再判断在哪个数组，再二分，其实是可以做到O(Log N)的，找分界的点的规则就是找到首个小于a[0]的元素，思路用老师4个转换问题的解法就可以。按评论做了下leetcode33题，感觉会比较老师给的思考题描述清晰。。因为老师说的找问题，没有明确有几组循环数组。。 6
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;
}展开 3 5
2018-10-271. 先二分遍历找到分隔点index，特征是<pre, >=next;
2. 把数组分成二个部分，[0,index-1], [index,length-1];
3. 分别使用二分查找，找到给定的值。
时间复杂度为2*log(n). 不确定有什么更好的办法。 5
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;
}展开 4
2018-12-23第一次见到逻辑这么清晰的二分查找代码，已经被老师俘获了，太优雅了 4
2018-11-16老师，我有一个疑问。
使用二分查找的前提是有序数组。
对于本节IP地址问题，我们先进行排序再进行查找，我理解应该时间复杂度是排序平均O(nLogn)再加上二分查找O(logn)
比单纯的顺序遍历O(n)要慢许多了。
是不是实际中，这种无序情况直接使用了顺序遍历查找呢？ 2 4
2019-05-28我觉得查找第一个符合给定的值得那两种写法 第一种更好理解 没看懂作者的写法 2 3
2018-10-26给原来的index加上偏移量。
比如原来的二分查找代码从0开始到n-1结束，现在为x到x - 1 (即n-1+x-n)。
x为开始循环处的索引，例子里为3 （1所在索引）。需要扫描一遍数组找到x，复杂度O(n)。其余和普通二分查找一样，需要多判断index not out of bound。如果索引超过n了要减n。
总的复杂度还是O(n) 3
2019-11-18文中的二分查找四道题实现：
1.
public static int searchFirst(int[] array, int num) {
int l = 0;
int h = array.length - 1;
while (l < h) {
int mid = (l + h) >>> 1;
if (array[mid] < num) {
l = mid + 1;
} else {
h = mid;
}
}
if (array[l] == num) {
return l;
}
return -1;
}
2. public static int searchFirstLarge(int[] array, int num) {
int l = 0;
int h = array.length - 1;
while (l < h) {
int mid = (l + h) >>> 1;
if (array[mid] < num) {
l = mid + 1;
} else {
h = mid;
}
}
if (array[l] >= num) {
return l;
}
return -1;
}
3. public static int searchLast(int[] array, int num) {
int l = 0;
int h = array.length - 1;
while (l < h) {
int mid = (l + h + 1) >>> 1;
if (array[mid] > num) {
h = mid - 1;
} else {
l = mid;
}
}
if (array[l] == num) {
return l;
}
return -1;
}
4. public static int searchLastSmall(int[] array, int num) {
int l = 0;
int h = array.length - 1;
while (l < h) {
int mid = (l + h + 1) >>> 1;
if (array[mid] > num) {
h = mid - 1;
} else {
l = mid;
}
}
if (array[l] <= num) {
return l;
}
return -1;
}展开 2
2019-11-09想到一种思路，依旧对半查找，但是现在两边会出现一个有序数组和循环数组，如果选择的数在有序数组内，正常的二分查找就OK，如果不是，继续对半，同上。次数和二分查找一致，所以依旧是logN，就是判断比较多点。 2
2018-12-18public int search(int[] nums, int target) {
if(nums.length ==0) return -1;
if(nums.length ==1){
if(nums[0] == target) return 0;
else return -1;
}
int low = 0;
int high = nums.length - 1;
int index = subIndex(nums,low,high);
if(index != -1){
int val = binarySearch(nums,low,index,target);
if (val != -1) return val;
return binarySearch(nums,index+1,high,target);
}
return binarySearch(nums,low,high,target);
}
public static int subIndex(int [] nums,int low,int high){
while (low <= high){
int mid = low + ((high - low )>> 1);
if(nums.length < 1) return -1;
if(nums[mid] > nums[mid+1]) return mid;
else if( nums[mid] < nums[low] ) high = mid ;
else if (nums[mid] > nums[high]) low = mid ;
else return -1;
}
return -1;
}
public static int binarySearch(int[] nums,int low,int high,int target){
while (low <= high){
int mid = low + ((high - low)>>1);
if(nums[mid] == target) return mid;
else if (nums[mid] < target) low = mid + 1;
else high = mid -1;
}
return -1;
}展开 2
2018-12-10老师，你说二分查找更适合用在“近似”查找问题，在这类问题上，二分查找的优势更加明显。这种问题链式哈希表不是更擅长吗？作者回复: 哈希表是精准查找
2