[Java知识库]Java语言实现二分查找（可查询重复数据）

二分查找

1.前言

二分查找是一种查询效率非常高的查找算法，又称为折半查找。

用递归思想来实现二分查找较为形象并且代码可读性强，因此本文中将介绍二分查找的思想，代码实现以及重复值查找的拓展。

2.算法思想

使用二分查找的前提是在一组有序的序列下进行，每次以序列的中间位置的数作为标准与带查找的数进行比较，从而调整查找方向，并且缩小查找范围，直至匹配成功。

3.图示

4.优缺点

• 优点：比较次数少，查找速度快，平均性能较好
• 缺点：要求待查表为有序表，并且插入删除困难

因此二分查找适用于不经常变动且查找频繁的有序列表。

5.代码实现

标准二分查找

/**
 *
 * @param array     有序数组
 * @param left      左边的索引
 * @param right     右边的索引
 * @param findValue 要查找的值
 * @return   如果找到返回下标 否则返回-1
 */
public static int binarySearch(int[] array,int left,int right,int findValue)
{
    //更新mid值从而缩小查找范围
    int mid = (left + right)/2;
    //作为查找标准 通过比较midValue和findValue来调整查找方向
    int midValue = array[mid];

    //递归终止条件
    //-->当left索引值移动至right右方则说明该序列表已经查找完毕,但仍然未匹配到相等的值
    if (left > right)
    {
        return -1;
    }
    
    //查找的值在标准值右方
    if (findValue > midValue)
    {
        //调整left值,向右递归
        return binarySearch(array, mid+1, right, findValue);
    }
    //查找的值在标准值左方
    else if (findValue < midValue)
    {
        //调整right值,向左递归
        return binarySearch(array, left, mid-1, findValue);
    }
    //匹配成功
    else
    {
        //返回索引值
        return mid;
    }
}

测试

/**
 * 二分查找的前提:数组是有序的
 * @param args
 */
public static void main(String[] args)
{
    int[] array = {1,8,10,89,1000,1989};
    int index = binarySearch(array, 0, array.length-1, 1000);
    System.out.println(index);
}

//---------------------------------------------------测试结果------------------------------------------------------
待查找的值为1000,在该序列中的索引值为:4

拓展：可以查询重复值

/**
 * 思路分析:
 *    1.在找到查找的值的索引值时不要立刻返回索引
 *    2.在索引值左边进行遍历，将所有等于当前索引值的元素下表添加到集合ArrayList中
 *    3.在索引值右边进行遍历，将所有等于当前索引值的元素下表添加到集合ArrayList中
 *    4.返回ArrayList
 * @param array     数组
 * @param left      左边的索引
 * @param right     右边的索引
 * @param findValue 要查找的值
 * @return   如果找到返回下标 否则返回-1
 */
public static List<Integer> binarySearchMut(int[] array,int left,int right,int findValue)
{
    int mid = (left + right)/2;
    int midValue = array[mid];
    //存储索引值的列表
    ArrayList<Integer> arrayList = new ArrayList<>();
    if (left > right)
    {
        //如果没有找到值返回-1
        arrayList.add(-1);
        return arrayList;
    }

    if (findValue > midValue)
    {
        return binarySearchMut(array, mid+1, right, findValue);
    }else if (findValue < midValue)
    {
        return binarySearchMut(array, left, mid-1, findValue);
    }else
    {
        //用于左右遍历查找相同值的辅助遍历指针
        int temp = mid - 1;
		
        //向左遍历
        while (true)
        {
            if (temp < 0 || array[temp] != midValue)
            {
                break;
            }
            arrayList.add(temp);
            temp--;
        }

        arrayList.add(mid);

        temp = mid + 1;
        //向右遍历
        while (true)
        {
            if (temp > array.length - 1 || array[temp] != midValue)
            {
                break;
            }
            arrayList.add(temp);
            temp++;
        }

        return arrayList;
    }
}

以上。

如有不足或错误欢迎评论指正。