算法-二分查询、拆半查询

叁歲伎倆 2024-02-17 22:19 31阅读 0赞

算法-二分查询、拆半查询  
  
  
1.它的基本思想是：将n个有序的排列的元素分成个数大致相同的两半，取a\[n/2\]与欲查找的x作比较。  
  
  
2.比较结果有三种情况：  
2.1 如果x=a\[n/2\]则找到x，算法终止。  
2.2 如 果x<a\[n/2\]，则我们只要在数组a的左半部继续搜索x（这里假设数组元素呈升序排列）。  
2.3 如果x>a\[n/2\]，则我们只要在数组a的右 半部继续搜索x。  
  
  
3.二分查询步骤  
目标=33  
二分查询步骤：  
第1步：22,27,33,37,43,47,53,57,63,67,  
第2步：22,27,33,37,  
第3步：33,37,  
结果=33

实例代码：

@Test
    	public void test(){  
    	        Integer[] arr={22,27,33,37,43,47,53,57,63,67};  
    	        
    	        Integer kw=33;  
    	        System.out.println("目标="+kw);  
    	        Integer result = binarySearch(arr,kw);  
    	        System.out.println("结果="+result);  
    	}  
    	  
    	public int binarySearch(Integer[] arr, int keyword) {  
    	    int min = 0;  
    	    int max = arr.length - 1;
    	    int i=0;
    	    System.out.println("二分查询步骤：");
    	    while (min <= max && min <=arr.length - 1 && max <= arr.length - 1) {
    	        i++;	
    	        printStep(arr,i,max,min);    	
    	        int middle = (max + min) >> 1; //右移一位，相当于除以2，即：（max+min）/2  
    	        if (keyword == arr[middle]) {//中间值等于目标值，责返回
    	            return arr[middle]; //返回结果  
    	        } else if (keyword < arr[middle]) {//目标值小于中间值，截止索引=中间值-1  
    	            max = middle - 1;  
    	        } else { //目标大于中间值，开始索引=中间值+1；  
    	            min = middle + 1;  
    	        }
    	    }  
    	    return -1; //没有查到结果  
    	}   
    	public void printStep(Integer[] arr,int index,int max,int min){
    		System.out.print("第"+index+"步：");
    		for(int n=min;n<=max;n++){
    			System.out.print(arr[n]+",");
    		}
    		System.out.println();
    	}