专栏首页LeetCode2个线性表查找的优化
原创

2个线性表查找的优化

1.无序表的查找优化

问题:在一个无序的数组中查找是否存在目标值target;

解法一:

这恐怕是最为直接,最容易想到的解法了!

public boolean squenceSearch(int [] arr,int target){
    if (arr == null || arr.length == 0) return false;
    for (int i= 0 ; i< arr.length;i++){
        if (arr[i] == target) return true;
    }
    return false;
}

解法二:

设置arr[0]为target,称之为哨兵。

public int squenceSearchII(int [] arr,int target){
    if (arr == null || arr.length == 0) return -1;
    if (arr[0] == target) return 0;
    int temp = arr[0];
    arr[0] = target;
    int i = arr.length-1;
    while (arr[i] != target) {
        i--;
    }
    arr[0] = temp;
    return i == 0 ? -1:i;
}

解法一,执行一次for循环需要两次判断,解法二只需要一次判断。

2.有序表的二分查找法的优化

在二分查找中,我们常常对mid的更新为:

mid = left +(right - left)/2;

你是否想过,为是1/2而不是1/4或1/3呢?

实际上,如果待查的数据比较均匀,那么1/2是一个很好的选择,一旦待查数据中的数据是极度不均匀的,那么就需要考虑插值查找法。

我们将1/2用 (target - arr[left])/(arr[right] - arr[left])代替,就是插值查找法。

于是mid的更新变为:

mid = left +(target - arr[left])/(arr[right]- arr[left])*(right - left);

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • <hashmap><双指针>最长子数组长度问题

    给定一个无序数组arr,其中元素可正,可负,可0,给定一个整数k。求arr所有的子数组中累加和为k的最长子数组长度。

    大学里的混子
  • 堆排序&&动态中位数

    heapify():  这里是指最大heapify。 我们只需要从  k = N / 2开始,  在k >= 1的条件下对 k 进行shiftDown(), 然...

    大学里的混子
  • <双指针问题>全是正数的数组累加和为k的最长子数组长度

    大学里的混子
  • 排序算法算法对比

    排序大的分类可以分为两种:内排序和外排序。在排序过程中,全部记录存放在内存,则称为内排序,如果排序过程中需要使用外存,则称为外排序。下面讲的排序都是属于内排序。...

    朱晓霞
  • 你对JavaScript的Array对象了解有多少?

    工作中,数组应用非常广泛,菜单、列表、banner图等等都会应用到数组,所以必须对数组的属性和方法非常熟练才OK,下面一起来了解一下。

    Javanx
  • [Go] Golang练习项目-快速排序的GO语言实现

    快速排序首先选一个基准(你也可以认为是要放到排序后数组正确位置的元素)pivot,然后将数组按照选取的基准 pivot 进行划分。而选取 pivot 的方式又有...

    陶士涵
  • 数据结构与算法 基础排序(O(n^2))

    不能直接找到一个比minIndex小的就swap,因为交换后比较的就是minIndex和后一个元素2个元素的比较 而不是minIndex和后面所有元素比较

    g小志
  • Data Structure_Sort Algorithm

    生成随机的n个数量的数组,输出数组每一个元素的内容。测试排序算法使用的标准就是运行时间和排序的正确性,所以需要一个验证正确性和计算排序时间的:

    西红柿炒鸡蛋
  • Sort Algorithm

    生成随机的n个数量的数组,输出数组每一个元素的内容。测试排序算法使用的标准就是运行时间和排序的正确性,所以需要一个验证正确性和计算排序时间的:

    西红柿炒鸡蛋
  • [图解] 堆排序

    大根堆与数组的关系:计算机中是没有堆或者树这种概念的,堆或者树需要使用基本的数据结构来实现,用数组表示一个大根堆的规律如下:

    CoderJed

扫码关注云+社区

领取腾讯云代金券