二分法查找----<算法>初学java

ywlYWL

二分法:
二分法查找适用于数据量较大时，但是数据需要先排好顺序。


优点:
时间复杂程度从O(n) 到O(log2n) 在数据较大时 节省了时间


原理主要就是折半查找

(0)设查找的数组区间为array[low, high]）
（1）确定该区间的中间位置K
（2）将查找的值T与array[k]比较。若相等，查找成功返回此位置；否则确定新的查找区域，继续二分查找。区域确定如下：a.array[k]>T 由数组的有序性可知array[k,k+1,……,high]>T;故新的区间为array[low,……，K-1]b.array[k]<T 类似上面查找区间为array[k+1,……，high]。每一次查找与中间值比较，可以确定是否查找成功，不成功当前查找区间将缩小一半，递归查找即可。-----(笔记来自百度)

今天遇到一算法题:
//给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
//
// 请必须使用时间复杂度为 O(log n) 的算法。

刚开始一看题 直接遍历不就行了?

的确可以 但时间复杂度为O(n)
能不能再减小呢?
能!
代码出来:

public int searchInsert(int[] nums, int target) {
int low=0;
int high=nums.length-1;
int ans=high;
while (low<=high){
int middle=(low+high)/2;
if (target==nums[middle]){
return middle;
}else if (target>nums[middle]){
low=middle+1;
}else if (target<nums[middle]){
high=middle-1;
}
}
return low;
}

今天收获 不错 明天加油!

1039468583

搜索曾经的回忆 发表于 2021-12-24 21:12
直接 high+(low-high)/2 不就好了吗,没必要定义long

如果high很大可能超过Int的最大值

ywlYWL

冷到吃雪糕 发表于 2021-12-24 19:22
int middle=(low+high)/2; 有bug，high太大加和就溢出了

太有道理了  改成long

冷到吃雪糕

int middle=(low+high)/2; 有bug，high太大加和就溢出了

搜索曾经的回忆

ywlYWL 发表于 2021-12-24 20:19
太有道理了  改成long

直接 high+(low-high)/2 不就好了吗,没必要定义long

1039468583

搜索曾经的回忆 发表于 2021-12-24 21:12
直接 high+(low-high)/2 不就好了吗,没必要定义long

high+(low-high)>>1

搜索曾经的回忆

1039468583 发表于 2021-12-24 22:47
high+(low-high)>>2

虽然但是，我还是觉得是>>1

orginly

我也在看算法了，感觉很容易忘

1039468583

搜索曾经的回忆 发表于 2021-12-24 22:48
虽然但是，我还是觉得是>>1

打错了 是 》》1

搜索曾经的回忆

1039468583 发表于 2021-12-25 12:14
打错了 是 》》1

不晓得你用的什么编程语言，java,C还有python都是>>