基本搜索算法 Binarysearch

输入输出描述

要求在有序数组A里，查找数值target

如果找到就返回索引 找不到返回-1

二分查找的算法基础版基本思路

首先确定两个指针 i j

设置指针和初值

i指向0 索引 j指向n-1索引

以规定范围

再执行中间值和目标值比较的逻辑

用循环实现 while（i<=j）

取到中间索引 再java里两个int（整数）相除自动取整

再判断

目标值小于中间值 j向左移动

目标值大于中间值 i向右移动

目标值等于中间值 返回索引 即为中间索引

代码实现

import java.util.Scanner;

public class Main {
    //简易版的二分查找法
    public static int[] arr =new int[]{1,2,3,4,5,6,7,8,9};
    public static void main(String[] args) {
        Scanner Dduo=new Scanner(System.in);
        System.out.println("请输入要查找的目标值");
        int target=Dduo.nextInt();
        if(Binarysearch(arr,arr.length,target)==-1)
            System.out.println("数组中不存在目标值");
        else
            System.out.println("目标值"+target+"的索引为"+Binarysearch(arr,arr.length,target));
    }
    public static int Binarysearch(int arr[],int n,int target){
        //初始化查找指针
        int i=0,j=n-1;
        //通过循环不断执行中间值和目标值比较的逻辑
        while(i<=j){
            //取到中间索引
            int m=(i+j)/2;
            //目标再左边
            if(target<arr[m])
                j=m-1;
            //目标再右边
            else if(target>arr[m])
                i=m+1;
            //找到了
            else return m;
        }
        return -1;
    }
}

小结

要注意目标值和中间索引对应的值比较时，是比较的大于还是小于

千千万万要考虑等于号

可以总结为三种情况

目标值大于中间索引所对应的数值 更新i数值

目标值小于中间索引所对应的数值 更新j数值

返回中间索引