欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

二分法查找(java递归与非递归实现)

程序员文章站 2024-03-17 23:10:16
...

非递归实现二分法查找

/**
 * 二分法查找 非递归实现
 */
public class BinarySearchNoRecur2 {
    public static void main(String[] args) {
        int array[]={1,3,8,10,11,67,100};
        int index = binarySearch(array,100);
        System.out.println("index="+index);
    }

    public static int binarySearch(int array[],int target){
        int left = 0;
        int right = array.length;
        while(left<=right){
            int mid = (left+right)/2;
            if(array[mid]==target){
                return mid;
            }else if(array[mid]<target){
                left = mid+1;
            }else{
                right = mid-1;
            }
        }
        return -1;
    }
}

递归实现二分法查找

/**
 * 二分法查找,递归实现
 */

public class BinarySearch {
    public static void main(String[] args) {
        int array[]={1,3,8,10,11,67,100};
         binarySearch(array,100,0,array.length-1);

    }
    public static void binarySearch(int array[],int target,int left,int right){
        int mid = (left+right)/2;

        if (left <= right) {
            if(array[mid]==target){
                System.out.println("index=" +mid);
            }else if(array[mid]>target){
                binarySearch(array,target,left,mid-1);
            }else if(array[mid]<target){
                binarySearch(array,target,mid+1,right);
            }else {
               return;
            }
        }
    }
}

相关标签: 算法