数据结构-递归

二分法查找

package com.execlib.search;

/**
 * 二分法查找
 */
public class BinarySearch {
    public int search(int[] data,int key){
        return binarySearch(data,key,0,data.length-1);
    }

    public int binarySearch(int[] data,int key, int left, int right) {
        if (left>=right)
            return -1;
        int mid = (left+right)/2;
        if (data[mid]>key){
            right = mid-1;
        }else if (data[mid]<key){
            left = mid+1;
        }else {
            System.out.println("找到数据：index="+mid);
            return mid;
        }
        return binarySearch(data,key,left,right);
    }

    /**
     * 非递归形式二分查找
     * @param data
     * @param key
     * @return
     */
    public int binarySearchNoCycle(int[] data,int key) {
        int left = 0;
        int right = data.length-1;
        int mid = 0 ;
        while (left<=right){
            mid = (left+right)/2;
            if (data[mid]>key){
                right = mid-1;
            }else if (data[mid]<key){
                left = mid+1;
            }else {
                System.out.println("找到数据：index="+mid);
                return mid;
            }
        }
        return -1;
    }

}