【java算法】二分查找算法详解_java二分法查找算法

hello，大家好！我是磨磨唧唧小蘑菇~

最近在努力的复习一些基本的算法，本期就以java的二分查找算法进行详细的概述（之前面试的时候，手写算法被坑过，一把泪啊）。进入正题吧~

目录

一、二分查找算法的介绍

二、二分查找算法的思路分析

三、二分查找算法的实例

一、二分查找算法的介绍

二分查找，又名折半查找。顾名思义，一半一半去找目标值~

对于一个有序的升序列表，将目标值与表中间的值进行对比：

1）如果目标值与表中间的值相等，则直接返回表中间的值即可

2）如果目标值与表中间的值不相等，则将两者进行大小比较，从而分成两个表：

（1）如果目标值小于中间值，说明目标值在中间值往左的表中，故舍弃中间值往右的表，重新二分查找中间值往左的表

（2）如果目标值大于中间值，说明目标值在中间值往右的表中，故舍弃中间值往左的表，重新二分查找中间值往右的表

最后，重复以上过程，直到找到目标值为止；或直到子表不存在为止，此时为查找不成功

二、二分查找算法的思路分析

1）首先确定有序的升序列表的中间值是多少

即：mid = （left+right）/2        //中间值的下标

2）将目标值target与表中间的值arr[mid]进行比较：

即：如果target = arr[mid]，说明目标值与arr[mid]相等，找到了目标值

       如果target < arr[mid]，说明目标值在arr[mid]的左边，因此需要接着二分查找左边的表

       如果target > arr[mid]，说明目标值在arr[mid]的右边，因此需要接着二分查找右边的表

Attention：什么时候需要结束呢？

1）找到目标值就结束

2）查找完整个数组，如果依然没有找到目标值，也需要结束

3）当left > right，则直接退出

三、二分查找算法的实例

eg：给你一个有序的升序数组，再给你一个目标值，请在数组中找到对应的目标值并返回它的下标

1、非递归算法实现：

package com.java.basic.array;
 
/**
 * @Author wangchuanmin
 * @Date 2021/9/1 17:35
 */
import java.util.Arrays;
/**
 * 二分查找算法
 */
public class BinarySearch {
    /**
     * 二分查找算法第一种：有序数组中没有重复的目标值（目标值是唯一的）---非递归
     * @param target
     * @param nums
     * @return
     */
    // 非递归实现
    public int binarySearch1(int target, int[] nums) {
        int left = 0;
        int right = nums.length-1;  //取最后一个下标
        int mid = 0;
        if (left > right || nums.length == 0 || nums == null) { //左下标大于右下标，直接返回-1
            return -1;
        }
        while (left <= right) { //初始化 right 的赋值是 nums.length - 1，即最后一个元素的索引，而不是 nums.length
            mid = (left + right)/2; //如果下标之和除以2有小数，则直接去掉0.5
            if (target == nums[mid]) {
                return mid; //找到目标值，然后返回
            } else if (target > nums[mid]) {    //目标值大于中间值，向右遍历
                left = mid + 1; //所以向右遍历的第一个下标是：中间下标+1
            } else if (target < nums[mid]) {    //目标值小于中间值，向左遍历
                right = mid - 1;    //所以向左遍历的最后一个下标是：中间下标-1
            }
        }
        return -1;  //找不到对应目标值，直接返回-1
    }
 
 
    public static void main(String[] args) {
        BinarySearch bSearch = new BinarySearch();
        int target = 9;
        int[] nums = new int[]{9,3,4,6,8};
        Arrays.sort(nums);
        System.out.println("排序后的nums为：" + Arrays.toString(nums));
        int result = bSearch.binarySearch1(target,nuns);
        System.out.println("非递归算法，目标" + target + "的下标是：" + result);
    }
}

运行结果如下：

排序后的nums为：[3, 4, 6, 8, 9]
非递归算法，目标9的下标是：4
 
Process finished with exit code 0

2、递归算法实现：

package com.java.basic.array;
 
/**
 * @Author wangchuanmin
 * @Date 2021/9/1 17:35
 */
import java.util.Arrays;
/**
 * 二分查找算法
 */
public class BinarySearch {
    /**
     * 二分查找算法第二种：有序数组中没有重复的目标值（目标值是唯一的）---递归
     * @param target
     * @param nums
     * @param left
     * @param right
     * @return
     */
    public int binarySearch2(int target, int[] nums, int left, int right) {
        int mid = (left + right)/2;
        if (nums.length == 0 || nums == null || left > right) {
            return -1;
        }
        while (left <= right) {
            if (target == nums[mid]) {
                return mid;
            } else if (target < nums[mid]) {
                return binarySearch2(target, nums, left, mid - 1);
            } else if (target > nums[mid]) {
                return binarySearch2(target, nums, mid + 1, right);
            }
        }
        return -1;
    }
 
 
 
    public static void main(String[] args) {
        BinarySearch bSearch = new BinarySearch();
        int target = 8;
        int[] nums = new int[]{9,3,4,6,8};
        Arrays.sort(nums);
        System.out.println("排序后的nums为：" + Arrays.toString(nums));
        int result1 = bSearch.binarySearch2(target, nums, 0, nums.length-1 );
        System.out.println("递归算法，目标" + target + "的下标是：" + result1);
    }
}

运行结果如下：

排序后的nums为：[3, 4, 6, 8, 9]
递归算法，目标8的下标是：3
 
Process finished with exit code 0

以上的两种方法，仅适用于“目标值是唯一”。如果相同目标值有多个的话，就不适用啦~（目前还没想明白，如果有多个目标值的时候，该怎么办？）哎，真是苦恼呢QAQ

好啦，到这里java的二分查找算法就结束啦~欢迎交流;-)