jjzjj

二分查找步骤及问题总结

Weloe's Blog 2023-03-28 原文

二分查找

参数： 有序数组arr(这里按升序来讲)，待搜索的值target

步骤

  1. 定义左边界left和有边界right
  2. 获取中间索引(整数) mid = (left+right)/2，注意：js只有小数，mid需要再取整
  3. 中间索引的值arr[mid]与待搜索的值target进行比较
    • arr[mid] == target ，即为找到，返回中间索引mid
    • arr[mid] > target，说明要搜索的值在mid的左边(降序情况相反)，需要去mid的左边找，更改右边界right为mid-1，重新查找
    • arr[mid] < target，说明要搜索的值在mid的右边(降序情况相反)，需要去mid的右边找，更改左边界left为mid+1，重新查找
  4. 查找(循环)的过程中如果left > right说明找不到target，结束查找

根据以上步骤可以写出递归、和非递归两种二分查找的方法

代码实现

    public static void main(String[] args) {
        int arr[] = {1, 8, 10, 11,23,1000,1234};
        //int resIndex = binarySearch(arr, 0, arr.length - 1, 11);
        int resIndex = binarySearchNoRecur(arr,11);
        System.out.println(resIndex);
    }
	


	/** 非递归二分查找
     * @param arr    待查找的数组(升序
     * @param target 需要查找的值
     * @return 返回对应下标，-1表示没有找到
     */
    public static int binarySearchNoRecur(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) { //说明需要继续查找
            int mid = (left + right) / 2;
            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] > target) {
                right = mid - 1;//向mid的左边
            } else {
                left = mid + 1;//向mid 的右边
            }
        }
        return -1;
    }

	/** 递归版二分查找
     * @param arr    待查找的数组(升序
     * @param target 需要查找的值
     * @return 返回对应下标，-1表示没有找到
     */
     public static int binarySearch(int[] arr, int left, int right, int target) {

        if (left > right) {
            return -1;
        }
        int mid = (left + right) / 2;
        int midVal = arr[mid];
        if (target > midVal) { //向右递归
            return binarySearch(arr, mid + 1, right, target);
        } else if (target < midVal) { //向左递归
            return binarySearch(arr, left, mid - 1, target);
        } else {//找到
            return mid;
        }
    }

整数溢出问题

出现原因：java 中的 int 总共就 32 位，正数上限的情况首位也只能是 0，其他位都可以是 1（就是 2^31-1 的情况）。但是如果正数过大了，例如 2^31，计算机不得不把首位变成 1，把它按照正常的方式输出了(把1作为符号位)，于是就成了负的值。

获取中间索引时(left + right) / 2，如果left和right都特别大，那么就有可能超出整数锁能存储的最大值，从而出现整数溢出问题

如下情况，第二次的mid出现了整数溢出问题

	int left = 0;
        int right = Integer.MAX_VALUE - 1;
        int mid = (left+right)/2;
        System.out.println(mid);
        //如果中间值小于目标值，需要更改左边界为mid+1
		left = mid + 1;
        mid = (left+right)/2;
        System.out.println(mid);

输出

1073741823
-536870913

如何避免？

方法一

把求中间值公式改为left - left/2 + right/2 =》left + (right - left)/2

由于两个大值相减(right - left)得到的值较小，就避免了溢出问题

方法二

无符号的右移运算代替除法

(left+right)/2 =》(left+right)>>>1

本来溢出的二进制数符号位为负数，由于进行了移位，就不把最高位当成符号位，就解决了溢出问题

二分二分查找midcoderight算法与数据结构

有关二分查找步骤及问题总结的更多相关文章

  1. ruby - 在 64 位 Snow Leopard 上使用 rvm、postgres 9.0、ruby 1.9.2-p136 安装 pg gem 时出现问题 - 2

    我想为Heroku构建一个Rails3应用程序。他们使用Postgres作为他们的数据库，所以我通过MacPorts安装了postgres9.0。现在我需要一个postgresgem并且共识是出于性能原因你想要pggem。但是我对我得到的错误感到非常困惑当我尝试在rvm下通过geminstall安装pg时。我已经非常明确地指定了所有postgres目录的位置可以找到但仍然无法完成安装:$envARCHFLAGS='-archx86_64'geminstallpg--\--with-pg-config=/opt/local/var/db/postgresql90/defaultdb/po

  2. ruby - 通过 rvm 升级 ruby​​gems 的问题 - 2

    尝试通过RVM将RubyGems升级到版本1.8.10并出现此错误:$rvmrubygemslatestRemovingoldRubygemsfiles...Installingrubygems-1.8.10forruby-1.9.2-p180...ERROR:Errorrunning'GEM_PATH="/Users/foo/.rvm/gems/ruby-1.9.2-p180:/Users/foo/.rvm/gems/ruby-1.9.2-p180@global:/Users/foo/.rvm/gems/ruby-1.9.2-p180:/Users/foo/.rvm/gems/rub

  3. ruby - 通过 RVM (OSX Mountain Lion) 安装 Ruby 2.0.0-p247 时遇到问题 - 2

    我的最终目标是安装当前版本的RubyonRails。我在OSXMountainLion上运行。到目前为止，这是我的过程:已安装的RVM$\curl-Lhttps://get.rvm.io|bash-sstable检查已知(我假设已批准)安装$rvmlistknown我看到当前的稳定版本可用[ruby-]2.0.0[-p247]输入命令安装$rvminstall2.0.0-p247注意:我也试过这些安装命令$rvminstallruby-2.0.0-p247$rvminstallruby=2.0.0-p247我很快就无处可去了。结果:$rvminstall2.0.0-p247Search

  4. ruby - Fast-stemmer 安装问题 - 2

    由于fast-stemmer的问题，我很难安装我想要的任何ruby​​gem。我把我得到的错误放在下面。Buildingnativeextensions.Thiscouldtakeawhile...ERROR:Errorinstallingfast-stemmer:ERROR:Failedtobuildgemnativeextension./System/Library/Frameworks/Ruby.framework/Versions/2.0/usr/bin/rubyextconf.rbcreatingMakefilemake"DESTDIR="cleanmake"DESTDIR=

  5. ruby - 当使用::指定模块时，为什么 Ruby 不在更高范围内查找类？ - 2

    我刚刚被困在这个问题上一段时间了。以这个基地为例:moduleTopclassTestendmoduleFooendend稍后，我可以通过这样做在Foo中定义扩展Test的类:moduleTopmoduleFooclassSomeTest但是，如果我尝试通过使用::指定模块来最小化缩进:moduleTop::FooclassFailure这失败了:NameError:uninitializedconstantTop::Foo::Test这是一个错误，还是仅仅是Ruby解析变量名的方式的逻辑结果？ 最佳答案 Isthisabug,or

  6. ruby - 安装 Ruby 时遇到问题(无法下载资源 "readline--patch") - 2

    当我尝试安装Ruby时遇到此错误。我试过查看this和this但无济于事➜~brewinstallrubyWarning:YouareusingOSX10.12.Wedonotprovidesupportforthispre-releaseversion.Youmayencounterbuildfailuresorotherbreakages.Pleasecreatepull-requestsinsteadoffilingissues.==>Installingdependenciesforruby:readline,libyaml,makedepend==>Installingrub

  7. ruby - 查找字符串中的内容类型(数字、日期、时间、字符串等) - 2

    我正在尝试解析一个CSV文件并使用SQL命令自动为其创建一个表。CSV中的第一行给出了列标题。但我需要推断每个列的类型。Ruby中是否有任何函数可以找到每个字段中内容的类型。例如，CSV行:"12012","Test","1233.22","12:21:22","10/10/2009"应该产生像这样的类型['integer','string','float','time','date']谢谢! 最佳答案 require'time'defto_something(str)if(num=Integer(str)rescueFloat(s

  8. java - 从 JRuby 调用 Java 类的问题 - 2

    我正在尝试使用boilerpipe来自JRuby。我看过guide从JRuby调用Java，并成功地将它与另一个Java包一起使用，但无法弄清楚为什么同样的东西不能用于boilerpipe。我正在尝试基本上从JRuby中执行与此Java等效的操作:URLurl=newURL("http://www.example.com/some-location/index.html");Stringtext=ArticleExtractor.INSTANCE.getText(url);在JRuby中试过这个:require'java'url=java.net.URL.new("http://www

  9. ruby-on-rails - 简单的 Ruby on Rails 问题——如何将评论附加到用户和文章？ - 2

    我意识到这可能是一个非常基本的问题，但我现在已经花了几天时间回过头来解决这个问题，但出于某种原因，Google就是没有帮助我。(我认为部分问题在于我是一个初学者，我不知道该问什么......)我也看过O'Reilly的RubyCookbook和RailsAPI，但我仍然停留在这个问题上.我找到了一些关于多态关系的信息，但它似乎不是我需要的(尽管如果我错了请告诉我)。我正在尝试调整MichaelHartl'stutorial创建一个包含用户、文章和评论的博客应用程序(不使用脚手架)。我希望评论既属于用户又属于文章。我的主要问题是:我不知道如何将当前文章的ID放入评论Controller。

  10. 【高数】用拉格朗日中值定理解决极限问题 - 2

    首先回顾一下拉格朗日定理的内容：函数f(x)是在闭区间[a,b]上连续、开区间(a,b)上可导的函数，那么至少存在一个，使得:通过这个表达式我们可以知道，f(x)是函数的主体，a和b可以看作是主体函数f(x)中所取的两个值。那么可以有，  也就意味着我们可以用来替换 这种替换可以用在求某些多项式差的极限中。方法： 外层函数f(x)是一致的，并且h(x)和g(x)是等价无穷小。此时，利用拉格朗日定理，将原式替换为 ，再进行求解，往往会省去复合函数求极限的很多麻烦。使用要注意：1.要先找到主体函数f(x)，即外层函数必须相同。2.f(x)找到后，复合部分是等价无穷小。3.要满足作差的形式。如果是加

随机推荐