简单二分

你的名字 2021-09-28 17:10 273阅读 0赞

二分查找是极有效率的算法，它的时间复杂度为O（log N），这里使用两个小案例简单分析。

递归搜索需要进行排序，否则无法进行，Arrays类提供的BinarySearch方法也是一样的。为了找到某个值，把数据分成两部分，然后看所要查找的数在哪一个范围，如果不在另一个范围则把搜索的范围缩小一半。代码如下：

public class 递归二分查找 {
        public static void main(String[] args) {
            int[] arr =  {1,2,4,5,6,7,8,9,10,14,16,47,59};
            System.out.println(binarySearch(arr,0,arr.length,8));
        }
        static int binarySearch(int[] arr,int  low,int high,int key) {
            int midIndex = low + ((high-low)>>1);
            int midVal = arr[midIndex];
            if(key < midVal) {
                return  binarySearch(arr,low,midIndex-1,key);
            }else if(key > midVal) {
                return  binarySearch(arr,midIndex+1,high,key);
            }else {
                return midIndex;
            }
        }
    }

这里是指数的二分，每次指数以平方级数增长。代码如下：

public class 求x的n次幂 {
        public static double myPow(double x, int n)  {
            double res = 1.0;
            for(int i = n; i != 0; i /= 2){//最终i的值为1,0终止循环
                x *= x;
                if(i % 2 != 0){//如果i/=2的结果是奇数则需要多乘以一个x,若为偶数则仅执行下方的 x=x*x
                    res *= x;
                }
            }
            return  n < 0 ? 1 / res : res;
        }
        public static void main(String[] args) {
            System.out.println(myPow(2.2200,500));
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，273人围观）

还没有评论，来说两句吧...

相关阅读

相关分块+二分

是令人难忘的一个晚上一个区间加1 然后求中位数的题，二分T了原因是每次只是加1 不用每次都二分答案。 [https://vjudge.net/contest...

雨点打透心脏的1/2处/ 2024年04月18日 08:26/ 0 赞/ 70 阅读

相关简单算法之二分查找

二分查找算法介绍二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键

水深无声/ 2023年10月09日 15:38/ 0 赞/ 59 阅读

相关简单的分页插件的实现(篇二)

插件(我是IDEA使用的) <!-- https://mvnrepository.com/artifact/com.github.pagehelper/pagehel

た入场券/ 2023年10月06日 11:03/ 0 赞/ 22 阅读

相关简单实现分页

实现分页！利用sql语句。 mysql的话就是利用limit ![这里写图片描述][SouthEast] 就在DAO类中增加有一个方法 findPage();

- 日理万妓/ 2022年07月13日 07:52/ 0 赞/ 290 阅读

相关 php简单分页

php简单分页 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.

骑猪看日落/ 2022年05月30日 09:18/ 0 赞/ 305 阅读

相关 vue 简单分页

vue 简单分页样式： .page-bar { -webkit-touch-callout: none; -web

谁借莪１个温暖的怀抱￠/ 2022年05月24日 08:00/ 0 赞/ 274 阅读

相关 Servlet简单分页

本文是参照易百教程上的[例子][Link 1]，觉得很有收藏价值，于是特记录一份数据库示例数据： DROP TABLE IF EXISTS `emplo

我不是女神ヾ/ 2022年05月22日 13:36/ 0 赞/ 230 阅读

相关二分

一、整数集合上的二分 1. 具体问题具体分析，左右半段哪个是可行区间，以及mid归属哪一半 2. 根据分析结果，选择一个配套形式 1. \\(r=mi

迈不过友情╰/ 2022年01月10日 04:37/ 0 赞/ 294 阅读

相关简单二分

二分查找是极有效率的算法，它的时间复杂度为O（log N），这里使用两个小案例简单分析。递归搜索需要进行排序，否则无法进行，Arrays类提供的BinarySearch方法

你的名字/ 2021年09月28日 17:10/ 0 赞/ 274 阅读

相关 php简单分页

<?php include('conn.php'); $sql = "select id from user"; //$totalsize = total...

灰太狼/ 2021年01月08日 14:33/ 0 赞/ 812 阅读