快捷導(dǎo)航

Java數(shù)據(jù)結(jié)構(gòu)與算法之二分查找詳解

更新時(shí)間：2023年12月18日 09:34:54 作者：暴躁的程序猿啊

這篇文章主要介紹了Java數(shù)據(jù)結(jié)構(gòu)與算法之二分查找詳解,二分查找算法是一種在有序數(shù)組中查找某一特定元素的搜索算法,其思想就是不斷地將有序查找表“一分為二”,逐漸縮小搜索區(qū)域,進(jìn)而找到目標(biāo)元素,需要的朋友可以參考下

Java二分查找

使用前提：二分查找需要在有序數(shù)組中進(jìn)行查找

需求

請(qǐng)對(duì)一個(gè)有序數(shù)組進(jìn)行二分查找{1,8,10,89,1000,1024}，輸入一個(gè)數(shù)字看看該數(shù)組中是否存在此數(shù)，并且求出下標(biāo)，如果沒有就返回“-1”

思路分析：

首先確定該數(shù)組的中間下標(biāo)

1.mid=(left+right)/2

2.然后讓需要查找的數(shù)findval和arr[mid]比較

findval>arr[mid]說明你要查找的數(shù)字在mid的右邊，因此需要遞歸的向右進(jìn)行查找
findval<arr[mid]說明你要查找的數(shù)字咋mid的左邊，因此需要遞歸的向左進(jìn)行查找
findval==arr[mid]說明找到，就返回

什么時(shí)候需要結(jié)束遞歸？

1.找到了數(shù)據(jù)就結(jié)束遞歸

2.遞歸完整個(gè)數(shù)組，仍然沒有找到findval，也需要結(jié)束遞歸當(dāng)left>right就需要退出

代碼實(shí)現(xiàn)

/**
 * 二分查找
 * 使用二分查找的前提 數(shù)組必須有序  從小到大 從大到小都可以
 *
 * @create: 2021/10/2
 * @author: Tony Stark
 */
public class BinarySearch {
    public static void main(String[] args) {
        int[] arr = {1, 8, 10, 89, 1000, 1024};
        int i = binarySearch(arr, 0, arr.length - 1, 1024);
        System.out.println(i);
    }
    /**
     * 二分查找的方法
     * @param arr  數(shù)組
     * @param left   左邊的索引
     * @param right   右邊的索引
     * @param findVal  要查找的值
     * @return  如果找到就返回下標(biāo)  ，沒有找到就返回-1
     */
    public static int binarySearch(int[] arr,int left,int right,int findVal){
        //當(dāng)left大于right時(shí)說明遞歸了整個(gè)數(shù)組但是沒有找到
        if (left>right){
            return -1;
        }
        //中間值的下標(biāo)
        int mid=(left+right)/2;
        //中間值
        int midVal=arr[mid];
        //如果要找的值大于中間值   向右遞歸  現(xiàn)在數(shù)組是從小到大  所以向右遞歸
        if (findVal>midVal){
              //向右遞歸
           return binarySearch(arr,mid+1,right,findVal);
        }else if(findVal<midVal){
            //如果要找的值小于中間值向左遞歸
            return binarySearch(arr, left,mid-1, findVal);
        }else if (findVal==midVal){
            //這種情況就是找到了那個(gè)數(shù)字
            return mid;
        }
        return -1;
    }
}

輸出