【Java练习】折半查找

╰+哭是因爲堅強的太久メ 2022-06-03 07:51 141阅读 0赞

需求：折半查找一个有序数组，找一个一个元素在数组中的角标位置。

思路：构造查找函数，若要查找的元素等于中间值，返回中间值的角标，不然返回-1。

/*
     需求：折半查找一个有序数组，找一个一个元素在数组中的角标位置。
    思路：构造查找函数，若要查找的元素等于中间值，返回中间值的角标，不然返回-1；
    步骤：
    1、（方案一）构造查找子函数Half1，参数列表为数组，查找值，返回类型为int；
    2、定义min、mid、max并初始化；
    3、while函数，循环条件为arry[mid]!=value；
    4、循环体内构造if语句，将value与arry[mid]比较，改变min、max、mid值;
    5、	找到了就跳出循环，return mid，否则return -1；
    6、主函数初始化一个有序数组，调用子函数并输出，构造子函数Half2（方案二）类似。
     */
    public class halfSearch 
    { 
    
    	public static void main(String[] args)
    	{
    		int [] arry= {2,3,4,5,6};
    		int index1=Half(arry,5);
    		int index2=Half2(arry,5);
    		System.out.println("index1="+index1+'\n'+"index2="+index2);
    
    	}
    	
    	/*
    	 折半查找方法1
    	 */
    	static int Half(int [] arry,int value)
    	{
    		
    		int min = 0, max = arry.length-1,mid = (min+max)/2;
    		while(arry[mid]!=value)
    		{
    			if(value<arry[mid])
    				max=mid-1;
    			else 
    				min=mid+1;
    			if(min>max)//找不到的情况下
    				return -1;//直接返回，比break跳出循环要方便
    			mid = (min+max)/2;
    		}
    		return mid;
    		
    	}
    	/*
    	 折半查找第二种方法
    	 */
    	static int Half2(int [] arry,int value)
    	{
    		int min = 0, max = arry.length-1,mid;
    		while(min<=max)
    		{
    			mid = (min+max)>>1;
    			if(value<arry[mid])
    				max=mid-1;
    			else if(value>arry[mid])
    				min=mid+1;
    			else
    				return mid;
    					
    		}
    		return -1;
    	}
    }

运行结果：

index1=3  
index2=3