【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的二分查找算法就结束啦~欢迎交流;-)