算法-在有序数组、无序数组中进行折半查找和二分法找无序数组中第k小（大）的数

66 阅读 0 评论 44 点赞

我是靠谱客的博主天真花瓣，最近开发中收集的这篇文章主要介绍算法-在有序数组、无序数组中进行折半查找和二分法找无序数组中第k小（大）的数，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

折半查找又称为二分查找或对分查找。

（1）基本的二分查找

使用条件：

1. 线性表中的记录必须按关键码有序。

2. 必须采用顺序存储结构。

基本思想：

在有序表中，取中间记录作为比较对象，

若给定值与中间记录的关键码相等，则查找成功。

若给定值小于中间记录的关键码，则在中间记录的左半区继续查找；

若给定值大于中间记录的关键码，则在中间记录的右半区继续查找。

不断重复上述过程，直到查找成功；或所查找的区域无记录，查找失败。

public class SearchBin {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
       int[] array = {05, 13, 19, 21, 37, 56, 64, 75, 80, 88, 92};
       int key = 21;
       int index = search_Bin(array, key);
       System.out.print(index);
	}
	
	/**
	 * 非递归的二分查找
	 * @param array  查找的数组
	 * @param key    要查找的关键字
	 * @return
	 */
	public static int search_Bin(int[] array, int key) {
		int low=0, high=array.length-1;
		while(low<=high) {
			int mid = (low + high)/2;
			if(array[mid]==key) {
				return mid;
			}else if(array[mid]>key) {
				high = mid - 1;
			}else {
				low = mid + 1;
			}
		}
		return 0;
	}

}

在有序表中的折半查找的时间效率是o(logN)。

（2）在无序数组中进行折半查找。

以前我了解的折半查找适用条件之一就是：在有序表中使用。那么，现在折半查找还可以用在无序数组中的查找，查找时间复杂度是O(NlongN)。

基本思想：

结合快排的思想，即每次选择一个关键字，先将比它大的数放在其右边，比它小的数放在其左边，然后比较它和要查找的数的关系，并选择下次迭代的区间。

public class disorderSearchBin {
	
	 public static int quickSortOneTime(int[] array, int low, int high){ //一趟快速排序   
		 int  key = array[low];  
         while(low < high){  
        	while(key < array[high] && low < high)  high--;
            array[low] = array[high];  
            while(key > array[low] && low < high)   low++;  
            array[high] = array[low];
         }  
	    array[high] = key;  
	    return high;
	    }  
	 
	 public static int twoDepart(int[] array,int low,int high, int key)  
	    {  
		    if(low <= high) { 
		    	int mid = quickSortOneTime(array, low, high);  
		    	System.out.println("mid = " + mid + " low = "+low+" high = " + high);  
		    	System.out.println(low < high);  
	            if(array[mid] == key) {   
	            	System.out.println("ok, keyword is at " +mid );
	            	return mid;
	            }else if (array[mid] < key) {  
	                low = mid +1;  
	                return twoDepart(array, low, high, key);  
	            } else if (array[mid] > key) {  
	                high = mid -1;  
	                return twoDepart(array, low, high, key);  
	            }  
	        } 
	        return 0;
	    }  

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		 int[] array = new int[] {92, 5, 88, 13, 80, 19, 75, 21, 64, 37, 56};  
	     int key = 13;  
	     int index = twoDepart(array, 0, array.length-1, key);
	     for(int i=0; i<array.length; i++) {
	    	 System.out.print(array[i]+" ");
	     }
	}
}

注意：最后，查找结束之后我们的数组已经是大致有序的数组了，不是原来的数组。

无序数组中使用二分查找算法的时间复杂度是O(NlogN)。

（3）二分法找无序数组中第K小的数

二分法能在无序数组中查找，也能实现用二分法在无序数组中找第k小的数。时间复杂度是O(NlongN)。

对上边代码做一点小的改动即可实现。

public class disorderSearchBin {
	
	 public static int quickSortOneTime(int[] array, int low, int high){ //一趟快速排序   
		 int  key = array[low];  
         while(low < high){  
        	while(key < array[high] && low < high)  high--;
            array[low] = array[high];  
            while(key > array[low] && low < high)   low++;  
            array[high] = array[low];
         }  
	    array[high] = key;  
	    return high;
	    }  
	 
	 public static int Select_k(int[] array, int low, int high, int k) {
		 int index;
		 if(low == high) return array[low];
		 int partition = quickSortOneTime(array, low, high);
		 index = partition - low + 1;  //找到的是第几个小值
		 if(index == k) {
			 return array[partition];
		 }else if(index < k) {//此时向右查找
			 return Select_k(array, partition+1, high, k-index);  //查找的是相对位置的值，k在右段中的下标为k-index
		 }else {
			 return Select_k(array, low, partition-1, k);
		 }
	 }

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		 int[] array = new int[] {92, 5, 88, 13, 80};   
	     int index = Select_k(array, 0, array.length-1, 5);
	     System.out.print(index);
	}
}

（4）二分法找无序数组中第K大的数

public class disorderSearchBin {
	
	 public static int quickSortOneTime(int[] array, int low, int high){ //一趟快速排序   
		 int  key = array[low];  
         while(low < high){  
        	while(key < array[high] && low < high)  high--;
            array[low] = array[high];  
            while(key > array[low] && low < high)   low++;  
            array[high] = array[low];
         }  
	    array[high] = key;  
	    return high;
	    }  
	 
	 public static int Select_k(int[] array, int low, int high, int k) {
		 int index;
		 if(low == high) return array[low];
		 int partition = quickSortOneTime(array, low, high);
		 index = high - partition + 1;  //找到的是第几个大值
		 if(index == k) {
			 return array[partition];
		 }else if(index < k) {//此时向左查找
			 return Select_k(array, low, partition-1, k-index);  //查找的是相对位置的值，k在左段中的下标为k-index
		 }else {
			 return Select_k(array, partition+1, high, k);
		 }
	 }

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		 int[] array = new int[] {92, 5, 88, 13, 80};   
	     int index = Select_k(array, 0, array.length-1, 2);
	     System.out.print(index);
	}

}

时间复杂度是O(NlogN)。