代码编织梦想

public class BinarySearch {
    /**
     * @author JadeXu
     * @// TODO: 2020/12/7 二分查找
     * 思路:
     * 1、获取数组的中间值,先获取下标,方便多次查找
     * 奇数位的数组直接获取中间位,偶数位的数组获取中间的第一位或第二位都可,一般获取第一位(因为与奇数位获取中间值的方法一样)
     * 2、获取查找的区间范围,start:区间开始的下标,end:区间结束的下标
     * 3、判断查找的数和中间位的数是否相同
     * 相同时,直接返回需要的数据,跳出方法
     * 大于时,即数可能在中间值右边的区间内,此时start = mid+1,即mid往后移一位,就得到了中间值右边区间的开始下标
     * 小于时,即数可能在中间值左边的区间内,此时end = mid-1,即mid往前移一位,就得到了中间值左边区间的结束下标
     * 当一个区间里,开始下标小于等于结束下标时,该区间才是有效区间,才能继续查找。否则无效,返回找不到,跳出方法
     */
    //循环
    /**
     * @param arr 已经升序好的int[]
     * @param num 需要查找的数字
     * @return 找到则返回下标,没找到则返回-1
     */
    private static int binarySearchByCycle(int[] arr,int num) {
        int start = 0;
        int end = arr.length - 1;

        while (start <= end){
            int mid = (start + end) / 2;
            if(num == arr[mid]){
                return mid;
            }else if(num > arr[mid]){
                start = mid + 1;
            }else {
                end = mid - 1;
            }
        }
        return -1;
    }

    //递归
    /**
     * @param arr 已经升序好的int[]
     * @param num 需要查找的数字
     * @param start 区间开始下标
     * @param end 区间结束下标
     * @return 找到则返回下标,没找到则返回-1
     */
    private static int binarySearchByRecursion(int[] arr,int num,int start,int end) {
        int mid = (start + end) / 2;
        if(num == arr[mid]){
            return mid;
        }else if(num > arr[mid]){
            start = mid + 1;
        }else {
            end = mid - 1;
        }
        if(start <= end){
            mid = binarySearchByRecursion(arr,num,start,end);  //递归继续寻找
        }else {
            mid = -1;
        }
        return mid;
    }
}

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 本文链接: https://blog.csdn.net/qq_44089205/article/details/110825668

java 8新特性2 Stream、新的时间API-爱代码爱编程

  lambda 表达式简写。 public class Test { public static void main(String[] args) { // 消费型 Consumer<Integer> con = s->System.out.println(s); //简化 Consumer<Int

VHDL实现全加器-爱代码爱编程

VHDL实现全加器 1.一位全加器 全加器是能够计算低位进位的二进制加法电路,一位全加器(FA)的逻辑表达式为: F=A⊕B⊕Ci Co=Ci(A⊕B)+AB 其中A,B为要相加的数,Ci为进位输入;F为和,Co是进位输出 真值表如下: 原理图如下: 因此在设计实体时,选定三输入二输出: LIBRARY IEEE; USE IEEE.STD_LOGIC

多线程&并发总结-爱代码爱编程

1.java中实现多线程有几种方式 继承Thread类;实现Runnable接口; 实现Callable接口通过FutureTask 包装器来创建Thread线程; 使用ExecutorService、Callable、Future实现由返回结果的多线程(也就是使用ExecutorService来管理前面的三种方式)。 2.如何停止一个正在运行的线程

史上功能最全Web购物车实现(基于jsp+java+servlet+dao)包括后台图书管理、实现数据库分页等功能-爱代码爱编程

购物车实现 基本功能描述页面展示购物车数据库信息代码路径展示代码实现bean基本属性的配置dao路径下对数据库进行的处理首页代码BookServlet逻辑处理主页面展示页面cart.jsp购物车信息展示图书后台信息管理 基本功能描述 本项目实现的是一个可视化的购物车系统,其主要功能如下。 用户进入登录页面进行登录,登陆成功则跳转到购物车主页

java中遍历字符串的三种方式(String类的方法)-爱代码爱编程

1).toCharArray() 2).length(), charAt() 3).length(), substring(i ,i+1) public static void main(String[] args) { String str = "keep walking!!!"; //方法一 char[

MYSQL专题-MySQL三大日志binlog、redo log和undo log-爱代码爱编程

日志是mysql数据库的重要组成部分,记录着数据库运行期间各种状态信息。mysql日志主要包括重做日志(redo log)、回滚日志(undo log)、二进制日志(bin log)、错误日志(error log)、慢查询日志(slow query log)、一般查询日志(general log),中继日志(relay log)。作为开发,我们重点需要关注

leetcode 1 --- 两数之和-爱代码爱编程

1 题目 给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。 2 解法 struct haveOrigionIndexNumber { int origionIndex; int val

动态规划之凸多边形最优三角剖分-爱代码爱编程

凸多边形最优三角剖分 1 问题定义2 问题分析3 递归结构4 核心代码5 举例 1 问题定义 凸多边形:把一个多边形任意一边向两方无限延长成为一条直线,如果多边形的其他各边均在此直线的同旁,那么这个多边形就叫做凸多边形。。 除去自身A点,以及和自己连接的 2 个点之外,A点和余点间都存在一条弦,即n-3条; 这n-3条弦能划分出n-2个

^异或实现两数交换swap方法-爱代码爱编程

^运算具有交换律和结合律,可以看作是无进位的位相加运算 -> 自反:p ^ q ^ q = p 实现两数交换swap 原理: int temp = a^b; int a = temp ^ a = a ^ a ^ b = b; int b = temp ^ b = a ^b ^ b = a代码int a = 3; int b = 10; a = a

LeetCode 1641. 统计字典序元音字符串的数目--动态规划-爱代码爱编程

统计字典序元音字符串的数目给你一个整数 n,请返回长度为 n 、仅由元音 (a, e, i, o, u) 组成且按 字典序排列 的字符串数量。 字符串 s 按 字典序排列 需要满足:对于所有有效的 i,s[i] 在字母表中的位置总是与 s[i+1] 相同或在 s[i+1] 之前。 示例 1: 输入:n = 1 输出:5 解释:仅由元音组成的 5 个字

leetcode 2 --- 两数相加-爱代码爱编程

1 题目 给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。 如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。 您可以假设除了数字 0 之外,这两个数都不会以 0 开头。 2 解法 2.1 初版解法 /** * Definition for

5分钟了解一致性哈希算法-爱代码爱编程

前言 一致性哈希算法(Consistent Hashing)在分布式系统的应用还是十分广泛的,本文尽量结合业务场景快速讲解一致性哈希算法的应用及与其相关的话题。 1 分布式缓存 随着业务的扩展,流量的剧增,单体项目逐渐划分为分布式系统。对于经常使用的数据,我们可以使用Redis作为缓存机制,减少数据层的压力。因此,重构后的系统架构如下图所示: 优化