search.java

Java程序设计大学教程程序源代码

/**
 * <p>Title: 查找算法</p>
 *
 * <p>Description:  整数值的查找算法演示程序</p>
 * <p>演示顺序查找和折半查找算法</p>
 * <p>Copyright: Copyright (c) 2005</p>
 *
 * <p>Company: 刘艺</p>
 *
 * @author 刘艺
 * @version 1.0
 */
package jbookch5;


public class Search {
    //顺序查找
    public int sequentialSearch(int arr[], int key) {
        for (int k = 0; k < arr.length; k++)
            if (arr[k] == key)
                return k;       //  成功,返回该数组元素的位置（即索引）
        return -1;              // 失败,返回-1
    }
    
    //折半查找
    public int binarySearch(int arr[], int key) {
        int low = 0;				// 初始化
        int high = arr.length - 1;
        while (low <= high) {
            int mid = (low + high) / 2; // 取折半值
            if (arr[mid] == key)
                return mid;                     // 成功,返回该数组元素的位置（即索引）
            else if (arr[mid] < key)
                low = mid + 1;                  // 定位查找上半段
            else
                high = mid - 1;                // 定位查找下半段
        }
        return -1; // 失败,返回-1
    }
}