数据结构 -- 二分查找

一个懵懂的菜鸟

已于 2024-04-16 01:50:35 修改

阅读量1k

点赞数 26

分类专栏：数据结构与算法文章标签：数据结构 java 算法

于 2024-04-16 01:22:58 首次发布

本文链接：https://blog.csdn.net/m0_59748326/article/details/137801452

版权

本文详细介绍了二分查找算法的基本概念、实现方式，包括基本版、平衡版和Java版，以及处理重复元素和未找到元素的情况。重点讨论了不同实现中的比较逻辑和优化策略。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

本文主要梳理了二分查找算法的几种实现思路，基本概念参考 顺序、二分、哈希查找的区别及联系_生成一个大小为10万的有序数组,随机查找一个元素,分别采用顺序查找和二分查找方式-CSDN博客

1、基本概念

（1）前提条件：待查找数据必须有序。

（2）实现方式：在查找过程中，它先和中间的比较，如果等于就直接返回，如果小于就在前半部分继续使用二分法进行查找，如果大于则在后半部分继续使用二分法进行查找。

2、算法实现

2.1 基本版实现

package com.hh.algorithm.find;

public class BinarySearch {

    public static void main(String[] args) {
        int[] arr = {1,2,4,5,5,6,7,8,9,11,23};
        System.out.println(BinarySearch.binary(arr, 4));
    }
    public static int binary(int[] arr, int key) {
        int i = 0;
        int j = arr.length - 1;
        while (i <= j) {
            int mid = (i + j) >>> 1;
            if (key < arr[mid]) {
                j = mid - 1;
            } else if (key > arr[mid]) {
                i = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

}

问题1：为什么是 i<=j ，而不是 i<j？

（1）i==j：意味着 i，j 它们指向的元素也会参与比较；

（2）i<j：只意味着mid 指向的元素参与比较。

问题2：j - ((j - i) >> 1) 与 (i+j)/2都是相加除2，使用后者有没有问题？

当超出 int 的范围时，他会把最高位视为符号位。