算法小细节之数组某部分的中间位置的索引

给定一个数组的某个部分,这部分起始索引为L,结束索引为R,求这部分中间位置的索引。

1. int mid = (L + R) / 2

这个公式在数学上没有任何错误,通过这样的方式得到的mid值一定是L和R的中间值,但是在计算机中可能会造成数值越界的问题,如果L接近Integer.MAX_VALUE,R也接近Integer.MAX_VALUE,那么(L + R)将会越界,返回一个不正确的值,例如:

public static void main(String[] args) {

    int i1 = Integer.MAX_VALUE - 10;
    int i2 = Integer.MAX_VALUE - 20;
    int i3 = i1 + i2;
    
    System.out.println(i3);  // 结果是-32
}

虽然我们不会定义一个那么长的数组,但为了程序的绝对正确性,这个求中间索引的方法需要改进,就是下面的第二种方法。

2. int mid = L + (R - L) / 2

这种方法就避免了在计算机中的值越界问题,但还可以改进,看下面的第三种方法。

3. int mid = L + ((R - L) >> 1)

在计算机中,移位运算是要比算术运算的效率高的,我们知道,一个数右移一位的结果与这个数除以2的结果是相同的(关于位运算的详细介绍可以参考图解JAVA位运算),所以这样把除以2改为右移一位来提高运行效率。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏书山有路勤为径

1.C与C++

使用c++中的标准库类型vector可以很轻松的完成任务。 不需要管理内存分配,对不同的类型都可以处理

1324
来自专栏编程

Go语言中new和make的区别

Go语言中new和make是内建的两个函数,主要用来创建分配类型内存。在我们定义生成变量的时候,可能会觉得有点迷惑,其实他们的规则很简单,下面我们就通过一些示例...

1967
来自专栏深度学习与计算机视觉

算法-删除字符串中的公共字符

题目: 输入两个字符串,从第一字符串中删除第二个字符串中所有的字符。例如,输入“They are students.”和”aeiou”,则删除之后的第一个字...

2326
来自专栏python学习之旅

Python笔记(十七):生成器

Python生成器是创建迭代器的简单方法。简单来说,生成器是一个函数,它返回一个我们可以迭代的对象(迭代器)(一次一个值)。

851
来自专栏chenjx85的技术专栏

leetcode-22-括号生成

给出 n 代表生成括号的对数,请你写出一个函数,使其能够生成所有可能的并且有效的括号组合。

902
来自专栏从流域到海域

《笨办法学Python》 第40课手记

《笨办法学Python》 第40课手记 本节课讲述的字典,一种比数组更强大的数据结构,字典(dict)的另一个名称是散列(hash)。 我将在后面具体解释dic...

2087
来自专栏王磊的博客

把字符串转化为类型

问题:可以得到类型的String格式的名称,想要转化为相应的类型? ps:今天定义了好多个枚举类型,把枚举名称存放在一个ComboBox类名,控件值改变的时候要...

2675
来自专栏Phoenix的Android之旅

你不知道的HashMap

面试中经常会问到常用数据结构,比如HashMap。 相信你平时几乎每天都会用到HashMap,但是你知道它是的实现原理是怎样的吗? 这里先提几个问题:HashM...

1023
来自专栏数据小魔方

左手用R右手Python系列之——迭代器与迭代对象

接触过Python的小伙伴儿肯定都知道,Python中关于迭代器和可迭代对象运用的很广泛。迭代器可以以一种非常友好的方式使用在循环中,不仅节省内存,还能优化代码...

3838
来自专栏肖洒的博客

Python3学习集合

1713

扫码关注云+社区

领取腾讯云代金券