顺序查找JAVA实现设置哨兵

浏览数：45 / 时间：2015年06月08日

/**
 * 顺序查找，设置哨兵
 * 待查找数组:a[n]
 * 待查找元素:key
 * 
 * 方法：
 * b[n+1],其中，b[0]存放key,b[1]至b[n]存放a[0]至a[n-1]的元素
 * 将b[n]从后向前扫描，如果查找成功，返回元素在数组b中的下标，从1开始；如果查找失败，返回0
 * 
 * 设置哨兵的好处：避免了每次循环后都要检查数组下标是否越界
 * @author kpp
 *
 */
public class SequenSearch {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int data[] = {38,65,97,176,213,227,49,78,34,12,164,11,18,1};
        int key = 2;
        int index = search(data,key);
        if(index == 0){
            System.out.println("查找失败");
        }else{
            index = index - 1;
            System.out.println("查找成功，key在数组的第"+index+"个位置(从0开始)");
        }
        
    }

    /**
     * 
     * @param a    待查找数组
     * @param key  待查找元素
     * @return     如果查找成功，返回元素在数组b中的下标，从1开始；如果查找失败，返回0
     */
    private static int search(int a[],int key){
        int len = a.length;
        int b[] = new int[len+1];
        b[0] = key;
        System.arraycopy(a, 0, b, 1, len);
        
        int i = len;
        while(key != b[i]){
            i--;
        }
        return i;
    }
}