Java【数据结构】二分查找

这篇具有很好参考价值的文章主要介绍了Java【数据结构】二分查找。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

🌞 题目:

🌏在有序数组A中,查找目标值target
🌏如果找到返回索引
🌏如果找不到返回-1

算法描述 解释
前提 给定一个内含n个元素的有序数组A,满足A0<=A1<=A2<=·······<=An-1,一个待查值target
1 设置left=0;right = n - 1
2 如果left > right ,结束查找,没找到
3 设置mid = (left + right )/2,mid为中间索引
4 如果target < Am,设置right = mid -1,跳到第2步
5 如果target > Am,设置left = mid +1,跳到第2步
6 如果Am = target,结束查找,找到了

算法实现

 public  int binarySearch(int[] arr,int target) {
        int left = 0;
        int right = arr.length-1;
        while(left<=right) {
            int mid = (left+right)>>>1;
            if(target < arr[mid]) {
                right = mid - 1;
            }
            else if (arr[mid] < target) {
                left = mid + 1;
            }
            else {
                return mid;
            }
        }
        return -1;
    }

注解:

1.为什么while循环条件是left<=right,而不是left<right?
因为当left=right时,mid=left=right可能为我们想要查找的值

2.为什么mid = (left+right)>>>1,而不是(left+right)/2呢? >>>是无符号右移,无符号右移一位相当于除2取整。 不用(left+right)/2原因是,当left+right的值超过int类型的正整数最大范围,其值就会由正变负

在其他的资料中二分查找与这个代码不一样,

✈️ 二分查找的改动版

public static int binarySearch1(int[] arr,int target) {
        int left=0;
        int right = arr.length;      //第一处改动
        while(left < right) {        //第二处改动
            int mid = (left+right)>>>1;
            if(target < arr[mid]) {
                right = mid;          //第三处改动
            }
            else if (arr[mid] < target) {
                left = mid + 1;
            }
            else {
                return mid;
            }
        }
        return -1;
    }

⛵️注解:

right=arr.length,作为一个边界存在,left可能为我们的查找目标,但是right一定不是我们要找到的目标

🚀图解演示:

查找13
Java【数据结构】二分查找,java,数据结构,python

⛽️在Java中其实已经提供了二分查找的方法binarySearch

public class Test {
    public static void main(String[] args) {
        int[] arr ={1,2,3,4,5,5,6};
        int target = Arrays.binarySearch(arr,3);
        System.out.println(target);
       
    }
}

🚠运行结果:

2

Java【数据结构】二分查找,java,数据结构,python

🚩二分查找对重复元素的处理

📍重复元素最靠右的元素

说明:查找元素为重复元素的话,会查找到最右边的重复元素
Returns:
找到则返回最靠右索引
找不到返回-1

//重复元素最靠右的元素
public class Test5 {
    public static int binarySearch2(int[] arr,int target) {
        int left = 0;
        int right = arr.length-1;
        int cand = -1;
        while (left <= right) {
            int mid = (left + right)>>>1;
            if(target < arr[mid]) {
                right = mid-1;
            } else if (arr[mid] < target) {
                left = mid+1;
            }
            else {
                cand = mid;
               left = mid+1;
            }
        }
        return cand;
    }
}

说明:返回<=target的最右边的索引
Returns:
找到则返回最靠右索引
找不到返回小于target最右边的索引

 public static int binarySearchRightMost(int[] arr,int target){
        int left = 0;
        int right = arr.length-1;
        while(left <= right) {
            int mid = (left + right )>>>1;
            if(target < arr[mid]){
                right = mid-1;
            }
            else {
                left = mid + 1;
            }
        }
        return left-1;
    }

📍重复元素最靠左的元素

说明:查找元素为重复元素的话,会查找到最左边的重复元素
Returns:
找到则返回最靠左索引
找不到返回-1

 public static int binarySearch2(int[] arr,int target) {
        int left = 0;
        int right = arr.length-1;
        int cand = -1;
        while (left <= right) {
            int mid = (left + right)>>>1;
            if(target < arr[mid]) {
                right = mid-1;
            } else if (arr[mid] < target) {
                left = mid+1;
            }
            else {
                cand = mid;
                right = mid - 1;
            }
        }
        return cand;
    }

说明:
返回>=target最左边的索引
Returns:
找到则返回最靠左索引
找不到返回比target大的最左边索引

 public static int binarySearchLeftMost(int[] arr,int target) {
        int left=0;
        int right = arr.length-1;
        while(left <= right) {
            int mid = (left + right)>>>1;
            if(target <= arr[mid]) {
                right = mid - 1;

            }
            else  {
                left = mid + 1;
            }
        }
        return left;
    }

图解:
Java【数据结构】二分查找,java,数据结构,python

🚆leetcode二分查找题

1️⃣1.给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。
⏩ 链接: 二分查找

提示:
你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999,9999]之间。

class Solution {
    public int search(int[] nums, int target) {
        int i=0;
        int j = nums.length-1;
        while(i<=j){
           int m=(i+j)>>>1;
            if(target<nums[m]){
                j=m-1;
            }
            else if(nums[m]<target){
                i=m+1;
            }
            else{
                return m;
            }
        }
        return -1;
    }
}

2️⃣2.给定一个排序的整数数组 nums 和一个整数目标值 target ,请在数组中找到 target ,并返回其下标。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
⏩ 链接: 搜索插入位置

class Solution {
    public int searchInsert(int[] nums, int target) {
         int left=0;
        int right = nums.length-1;
        while(left <= right) {
            int mid = (left + right)>>>1;
            if(target <= nums[mid]) {
                right = mid - 1;

            }
            else  {
                left = mid + 1;
            }
        }
        return left;
    }
}

3️⃣3.给你一个按照非递减顺序排列的整数数组 nums,和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target,返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
⏩ 链接: 在排序数组中查找元素的第一个和最后一个位置文章来源地址https://www.toymoban.com/news/detail-656509.html

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int x=left(nums,target);
        if(x==-1){
            return new int[]{-1,-1};
        }
        else{
            return new int[]{x,right(nums,target)};
        }
    }
    public int left(int[] nums,int target) {
        int i=0;
        int j=nums.length-1;
        int cand=-1;
        while(i<=j){
           int  m=(i+j)>>>1;
            if(target<nums[m]){
                j=m-1;
            }
            else if(nums[m]<target){
                i=m+1;
            }
            else{
                cand=m;
                j=m-1;
            }
        }
        return cand;
    }
     public int right(int[] nums,int target) {
        int i=0;
        int j=nums.length-1;
        int cand=-1;
        while(i<=j){
          int  m=(i+j)>>>1;
            if(target<nums[m]){
                j=m-1;
            }
            else if(nums[m]<target){
                i=m+1;
            }
            else{
                cand=m;
                i=m+1;
            }
        }
        return cand;
    }
}

到了这里,关于Java【数据结构】二分查找的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构,查找算法(二分,分块,哈希)

    一、查找算法         1、二分查找:(前提条件: 必须有序的序列) 2、分块查找:(块间有序,块内无序)     索引表  +  源数据表     思路:     (1)先在索引表中确定在哪一块中     (2)再遍历这一块进行查找 //索引表 typedef  struct  {     int max; //块中最大值

    2024年02月11日
    浏览(59)
  • 数据结构-查找(顺序查找与二分查找的讲解与代码实现)

    顺序查找概念:从表的另一端开始,一次将记录的和给定值进行比较,若某个记录的和给定的值相等,则查找成功,反之则查找失败。 ASL:平均查找长度 pi查找概率,ci查找次数 eg:序列1,2,3 查找1的次数为1概率为1/3,2为两次概率1/3,3的次数为3概率1/3  将12

    2024年02月06日
    浏览(69)
  • 【手撕数据结构】二分查找(好多细节)

    🌈键盘敲烂,年薪30万🌈 目录 普通版本的二分查找: right只负责控制边界(少了两次比较): 时间复杂度更稳定的版本: BSLeftmost: BSRightmost:   🏸细节1:循环判定条件是left = right ⭐细节2:mid = (left + right ) 1 原因见代码注释 改动1:while条件是left right 改动2:right = nums.len

    2024年02月05日
    浏览(47)
  • 数据结构——用Java实现二分搜索树

    目录 一、树 二、二分搜索树 1.二叉树 2.二分搜索树 三、代码实现 1.树的构建 2.获取树中结点的个数 3.添加元素 4.查找元素 (1)查找元素是否存在 (2)查找最小元素 (3)查找最大元素 5.二分搜索树的遍历 (1)前序遍历: (2)中序遍历: (3)后序遍历: (4)层序遍历

    2024年02月19日
    浏览(41)
  • 数据结构和算法之二分法查找

    二分法查找,也称作 二分查找 或 折半查找 ,是一种在有序数组中快速查找特定元素的算法。它采用分治法思想,通过将问题划分为规模更小的子问题,并且通过对子问题的查找来解决原问题。 二分法查找的思路是不断地将数组一分为二,然后判断目标值在哪一部分,进而

    2024年02月09日
    浏览(47)
  • 二分搜索树(校招数据结构最低要求版)Java

    二分搜索树(Binary Search Tree,BST)是一种常见的数据结构,它能够高效地存储和查找数据。它的特点是每个节点都包含一个值,并且每个节点的左子树的值都小于节点的值,右子树的值都大于节点的值。 通过这种有序的排列方式,我们可以在二分搜索树中进行高效的查找操作

    2024年02月10日
    浏览(44)
  • 浙大数据结构第一周01-复杂度3 二分查找

    本题要求实现二分查找算法。 函数接口定义: 其中 List 结构定义如下: L 是用户传入的一个线性表,其中 ElementType 元素可以通过、==、进行比较,并且题目保证传入的数据是递增有序的。函数 BinarySearch 要查找 X 在 Data 中的位置,即数组下标(注意:元素从下标1开始存储)

    2024年02月12日
    浏览(47)
  • 【算法与数据结构】Java实现查找与排序

    也叫做折半查找,属于有序查找算法。 前提条件 :数组数据必须有序,从小到大,或者从大到小都是可以的。 如果是无序的,也可以先进行排序。 但是排序之后,会改变原有数据的顺序,查找出来元素位置跟原来的元素可能是不一样的,所以排序之后再查找只能判断当前数

    2024年01月19日
    浏览(50)
  • Java常见的数据结构:栈、队列、数组、链表、二叉树、二叉查找树、平衡二叉树、红黑树

    数据结构是计算机底层存储、组织数据的方式。是指数据相互之间是以什么方式排列在一起的。 通常情况下,精心选择的数据结构可以带来更高的运行或者存储效率 栈 队列 数组 链表 二叉树 二叉查找树 平衡二叉树 红黑树... 后进先出,先进后出 数据进入栈模型的过程称为

    2024年02月07日
    浏览(45)
  • Java学数据结构(2)——树Tree & 二叉树binary tree & 二叉查找树 & AVL树 & 树的遍历

    1.树的出现:解决链表线性访问时间太慢,树的时间复杂度O(logN); 2.二叉树的定义,最多两个儿子节点; 3.二叉查找树,左小,右大,中居中;remove方法,两种,只有一个儿子节点,有两个儿子节点; 4.AVL树,在二叉查找树基础上加平衡条件,旋转方法,单旋转,双旋转;

    2024年02月10日
    浏览(49)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包