首页 > 编程语言 >JavaSE-递归法解决二分查找、快速排序

JavaSE-递归法解决二分查找、快速排序

时间:2024-09-01 19:23:58浏览次数:12  
标签:二分 end 递归 nums int mid start JavaSE public

704. 二分查找icon-default.png?t=N7T8https://leetcode.cn/problems/binary-search/

package demo;

public class BinarySearch {

    public static void main(String[] args) {
        BinarySearch br=new BinarySearch();
        System.out.println(br.search(new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9}, 8));
    }
    public int search(int[] nums, int target) {
        int index=-1,mid= (int) Math.floor(nums.length/2);//默认为中间位置
        if(nums[mid]==target){
            index=mid;
        }else if(nums[mid]>target){// 向左查找
            index=search(nums,target,0,mid-1);
        }else{// 向右查找
            index=search(nums,target,mid+1,nums.length-1);
        }
        return index;
    }
    public static int search(int[] nums,int v,int start,int end){
        if(start>end){
            return -1;
        }
        int mid= (int) Math.floor((start+end)/2);
        if(nums[mid]==v){
            return mid;
        }else if(nums[mid]>v){
            return search(nums,v,start,mid-1);
        }else{
            return search(nums,v,mid+1,end);
        }
    }
}

牛客网——快速排序icon-default.png?t=N7T8https://www.nowcoder.com/questionTerminal/53d2f8d6f4e0472d83ee83a4d16f1b8f?page=1&onlyReference=false

package demo;

public class QuickSort {
    public static void main(String[] args) {
        QuickSort qs=new QuickSort();
        quickSort(new int[]{10,3,8,2,1,9,4,7,11},0,8);
    }
    public static void quickSort(int[] nums,int start,int end){
        // 递归结束条件
        if(start>=end){
            return;
        }
        int pivot=partition(nums,start,end);    // 返回pivot的位置
        quickSort(nums,start,pivot-1);  // 递归左子树
        quickSort(nums,pivot+1,end);    // 递归右子树
        System.out.println("当前节点为:"+pivot+"排序后的数组是");
        for (int i = 0; i < nums.length; i++) {
            System.out.print(nums[i]+" ");
        }
        System.out.println();
    }
    public static int partition(int[] nums,int start,int end){  // 快排的partition操作
        int pivot=nums[start];
        while(start<end){
            while(start<end&&nums[end]>=pivot){
                end--;
            }
            nums[start]=nums[end];
            while(start<end&&nums[start]<=pivot){
                start++;
            }
            nums[end]=nums[start];
        }
        nums[start]=pivot;
        return start;
    }
}

标签:二分,end,递归,nums,int,mid,start,JavaSE,public
From: https://blog.csdn.net/qq_64751004/article/details/141788471

相关文章

  • 二分查找
    题目:给定一个n个元素有序的(升序)整型数组nums和一个目标值target,写一个函数搜索nums中的target,如果目标值存在返回下标,否则返回-1。解法一:左闭右闭区间。(left=0,right=nums.length-1)思路:对于这种问题,捕捉到数据类型是数组并且数组中元素是有序的并且是查找类......
  • 信息学奥赛初赛天天练-81-NOIP2015普及组-完善程序-二分答案、二分查找、中位数、二分
    1完善程序(单选题,每小题3分,共30分)中位数median给定n(n为奇数且小于1000)个整数,整数的范围在0∼m(0<m<2^31)之间,请使用二分法求这n个整数的中位数。所谓中位数,是指将这n个数排序之后,排在正中间的数。(第五空2分,其余3分)01#include<iostream>02usingnamespace......
  • 学习笔记(?):一类查询 kth 的整体二分 trick
    问题大概就是有若干次修改(也有可能没有)和若干次查询,查询形如查某个范围的kth。做法是,把可能成为答案的候选集合按照权值大小排序。询问集合可以不用管顺序。然后开始二分。我们令solve(l,r,L,R)表示第\(l\)到\(r\)个询问的kth一定在候选序列的第\(L\)到\(R\)个数。......
  • NC 二分查找-II
    系列文章目录文章目录系列文章目录前言前言前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站,这篇文章男女通用,看懂了就去分享给你的码吧。描述请实现有重复数字的升序数组的二分查找给定一个元素有序的(升序)长......
  • 05.函数和递归
    5.函数和递归inlinefunctions---内联函数functiontemplate---函数模板5.1C++中的程序构件functionprototype---函数原型5.1.1函数原型Afunctionprototypeisadeclarationofafunctionthattellsthecompilerthefunction’sname,itsreturntypeand......
  • [Python手撕]二分法
    二分法二分法的几个位置比如01234567891233333456有时候想要寻找小于3的最大数字有时候想要寻找第一个满足>=3的数字,有时候想要寻找最后一个满足>=3的数字,有时候想要寻找小于4的最大数字nums=[1,2,3,4,5,5,5,5,5,6,7,8,9]n=......
  • F. Final Boss(二分,周期)
    题目来源:https://codeforces.com/contest/1985/problem/F//题意:你有n种攻击,每种攻击有周期和攻击力,如果当前回合是x,以为着第i种攻击,下次攻击是x+ci回合。现在有Boss,生命值为h,当h<=0的时候,Boss死亡。一开始所有攻击都没有冷却时间,问最少第几回合Boss死亡。//思路:“最开始无脑模......
  • 递归的实践1
    目录需求背景需求背景给你一个数组,把这个数组里面每个数字都求差,然后把这些差都求和。正常演示步骤:[1,3,5]1-3=21-5=4-3-5=2sum=8反过来思考子问题是什么:[1,3,5]reverse[5,3,1]5-3=25-1=4-3-1=2sum=8[1,3,5,7]reverse[7,5,3,1]7-5=......
  • shell脚本实现递归拷贝文件
    shell脚本#!/bin/bashlist=(10.12.63.23210.12.7.9510.12.8.24710.12.9.14610.253.1.19810.38.0.12510.38.0.20510.38.0.4410.38.0.9710.111.8.23410.12.20.1310.12.2.15010.12.3.14310.12.50.17510.12.65.710.12.8.12610.12.8.9010.1......
  • lambda实现递归
    lambda实现递归在C++中,lambda表达式在定义时实际上不能直接调用自己,因为lambda在定义时没有名字。要让一个lambda自我引用,你需要使用一个技巧:将lambda自身作为参数传递给自己,从而实现递归。为什么Lambda自身在定义时无法被调用?匿名性:Lambda表达式是匿名的,编译器在......