Java基础之折半查找法※※

快来打我* 2023-02-24 15:30 143阅读 0赞

import java.util.*;
    /*
    面试题：
    给定一个有序的数组，如果往该数组中存储一个元素，并保证这个数组还是有序的，
    那么个元素的存储的角标为如何获取。
    {
        13,15,19,28,33,45,78,106};
    */
    class ArrayDemo5 
    {
        
    	public static void main(String[] args) 
    	{
        
    //
    //		int[] arr = {
        4,1,8,7,3,8,2};
    		int[] arr = {
        13,15,19,28,33,45,78,106};
    		int index = halfSearch_2(arr,5);
    		System.out.println("index="+index);
    
    		int index1 = Arrays.binarySearch(arr,5);//如果存在返回的具体的角标位置，不存在返回的是  -插入点-1
    		System.out.println("index1="+index1);
    	}
    	/*
    	二分查找法。
    	
    	*/
    	public static int halfSearch(int[] arr,int key)
    	{
        
    		int max,min,mid;
    		min = 0;
    		max = arr.length-1;
    		mid = (max+min)/2;
    		
    		while(arr[mid]!=key)
    		{
        
    			if(key>arr[mid])
    				min = mid + 1;
    			else if(key<arr[mid])
    				max = mid - 1;
    
    			if(max<min)
    				return -1;
    
    			mid = (max+min)/2;
    		}
    		return mid;
    
    	}
    
    	public static int halfSearch_2(int[] arr,int key)
    	{
        
    		int max,min,mid;
    		min = 0;
    		max = arr.length-1;
    
    		while(min<=max)
    		{
        
    			mid = (max+min)>>1;
    
    			if(key>arr[mid])
    				min = mid + 1;
    			else if(key<arr[mid])
    				max = mid - 1;
    			else
    				return mid;
    		}
    		return -min-1;
    	}
    
    
    	/*
    	数组常见功能：查找。
    	*/
    	public static int getIndex(int[] arr,int key)
    	{
        
    		for(int x=0; x<arr.length; x++)
    		{
        
    			if(arr[x]==key)
    				return x;
    		}
    		return -1;
    	}
    }

折半查找  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDg1MzY2OQ_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDg1MzY2OQ_size_16_color_FFFFFF_t_70_pic_center_pic_center]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDg1MzY2OQ_size_16_color_FFFFFF_t_70]: /images/20230209/d58b5ecb681d4f45b96157649243b159.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDg1MzY2OQ_size_16_color_FFFFFF_t_70_pic_center_pic_center]: https://img-blog.csdnimg.cn/20201102112836336.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDg1MzY2OQ==,size_16,color_FFFFFF,t_70#pic_center#pic_center