二分法排序

二分法查找：不使用递归，时间复杂度是T(n) =O(logn)，空间复杂度：S(n) =O(1)
递归查找：时间复杂度是T(n) =O(logn)，空间复杂度：S(n) =O(logn)，得到相同的结果，递归会比较耗内存！

package com.yuan.tool;

import java.util.Arrays;

/**
 * FileName: 二分法排序
 * Author:   yhl
 * Date:     2019/12/1 0:59
 * Description: ${DESCRIPTION}
 */
public class 二分法排序 {

    public static void main(String[] args) {
        //给定数组
        int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        //给定要查找的值
        int key =10;
        //进行折半二分查找
        int index = binarySearch(array,key);
        //输出结果
        if(index == -1){
            System.out.println("不存在");
        }else{
            System.out.println(key+"的索引是"+index);
        }
    }
    /**
     * 不使用递归
     * T(n) =O(logn)
     * S(n) =O(1)
     * @param array
     * @param key
     * @return
     */
    public static int binarySearch(int [] array,int key){
        //指定low和high
        int low = 0;
        int high = array.length - 1;        
        
        //折半查找
        while(low <= high){
            //求得mid
            int mid = (low+high)/2;
            
            //判断是否等于
            if(key == array[mid]){
                return mid;
            }else if(key < array[mid]){
                high = mid -1;
            }else{ //key > array[mid]
                low = mid+1;
            }
        }       
        return -1;
    }
}

public class 递归查找{

    public static void main(String[] args) {
        //给定数组
        int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

        //给定要查找的值
        int key =60;
        
        //进行折半二分查找
        int index = binarySearch(array,key);
        
        //输出结果
        if(index == -1){
            System.out.println("不存在");
        }else{
            System.out.println(key+"的索引是"+index);
        }
    }
    
    
    /**
     * 使用递归
     * T(n) = O(logn)
     * S(n) = O(logn)
     * @param array
     * @param key
     * @return
     */
    public static int binarySearch(int [] array,int key){
        //指定low和high
        int low = 0;
        int high = array.length - 1;        
        return binarySearch(array, key, low, high);
        
    }
    
    
    public static int binarySearch(int [] array,int key,int low,int high){
        //递归的结束条件
        if(low > high){
            return -1;
        }
        int mid = (low + high) /2;
        if(key == array[mid] ){
            return mid;
        }else if(key < array[mid]){
            return binarySearch(array,key,low,mid-1);
        }else{//key >array[mid]
            return binarySearch(array,key,mid+1,high);
        }
    }