网站 › 『编程语言区』 › 二分法查找----<算法>初学java

ywlYWL 发表于 2021-12-24 19:15

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

本帖最后由 ywlYWL 于 2021-12-24 19:18 编辑

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


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


原理主要就是折半查找

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

今天遇到一算法题:
//给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
//
// 请必须使用时间复杂度为 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){
                return middle;
            }else if (target>nums){
                low=middle+1;
            }else if (target<nums){
                high=middle-1;
            }
      }
      return low;
    }
今天收获 不错 明天加油!

1039468583 发表于 2021-12-25 12:17

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

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

ywlYWL 发表于 2021-12-24 20:19

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

太有道理了改成long

冷到吃雪糕 发表于 2021-12-24 19:22

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

搜索曾经的回忆 发表于 2021-12-24 21:12

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

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

1039468583 发表于 2021-12-24 22:47

本帖最后由 1039468583 于 2021-12-24 22:49 编辑

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

搜索曾经的回忆 发表于 2021-12-24 22:48

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

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

orginly 发表于 2021-12-25 00:05

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

1039468583 发表于 2021-12-25 12:14

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

打错了 是 》》1

搜索曾经的回忆 发表于 2021-12-25 13:58

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

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

查看完整版本: 二分法查找----<算法>初学java