有序数组的二分查找

二分查找法是对一组有序的数字中进行查找，传递相应的数据，查找传递的数据对应的数组下标，没有找到返回-1；

有序数组二分查找的基本原理:因为数组是有序的，先找到中间位置的值，如果目标比这个值大，那么该目标必定在数组的右半部分，以此循环或者递归，一直找到这个数值为止。此算法的时间复杂度为O(logN),N为数组的长度 (2的X次方 == N，所以复杂度即为 O(logn) )

 

public class SortedArrayBinarySearch {
    
    public static void main(String[] args) {
        int[] source=new int[]{1,3,5,7,9,12}; 
        int key = 12;
        System.out.println(binaryRecurSearch(source, key));;
        System.out.println(binarySearchLoop(source, key));;
    }
    
    public static int binaryRecurSearch(int[] source, int key){
        return binarySearchRecursive(source, key,0,source.length-1);
    }
    

     //递归查找
    private static int binarySearchRecursive(int[] source, int key,int beginIndex,int endIndex){
        int midIndex = (beginIndex+endIndex)/2;
        if(key<source[beginIndex]  ||  key>source[endIndex] || beginIndex>endIndex){  
            return -1;  
        }  
        System.out.println("=======");
        if(key == source[midIndex]){
            return midIndex;
        }else if(key > source[midIndex]){
            return binarySearchRecursive(source, key, midIndex+1, endIndex);
        }else{
            return binarySearchRecursive(source, key, beginIndex, midIndex-1);
        }
        
    }
    
   //循环查找
    public static int binarySearchLoop(int[] source, int key){
        int beginIndex = 0;
        int endIndex = source.length-1;
        
        
        while(true){
            System.out.println("=======");
            if(key<source[beginIndex] || key>source[endIndex] ||  beginIndex>endIndex){  
                return -1;  
            }  
            int midIndex = (beginIndex+endIndex)/2;
            if(key == source[midIndex]){
                return midIndex;
            }else if(key > source[midIndex]){
                beginIndex = midIndex +1;
            }else{
                endIndex = midIndex -1;
            }
        }
        
    }

}

 

方式2：

/** 
     * 普通实现。 
     * @param srcArray 有序数组 
     * @param key 查找元素 
     * @return  不存在返回-1 
     */  
    public static int binSearch(int srcArray[], int key) {  
        int mid;  
        int start = 0;  
        int end = srcArray.length - 1;  
        while (start <= end) {  
            mid = (end - start) / 2 + start;  
            if (key < srcArray[mid]) {  
                end = mid - 1;  
            } else if (key > srcArray[mid]) {  
                start = mid + 1;  
            } else {  
                return mid;  
            }  
        }  
        return -1;  
    }  
	
	
/** 
     * 递归实现。 
     * @param srcArray  有序数组 
     * @param start 数组低地址下标 
     * @param end   数组高地址下标 
     * @param key  查找元素 
     * @return 查找元素不存在返回-1 
     */  
    public static int binSearch(int srcArray[], int start, int end, int key) {  
        int mid = (end - start) / 2 + start;  
        if (srcArray[mid] == key) {  
            return mid;  
        }  
        if (start >= end) {  
            return -1;  
        } else if (key > srcArray[mid]) {  
            return binSearch(srcArray, mid + 1, end, key);  
        } else if (key < srcArray[mid]) {  
            return binSearch(srcArray, start, mid - 1, key);  
        }  
        return -1;  
    }  

 

 

..