查找算法：线性查找，折半查找

 

线性查找

package com.search;

/**
 * JAVA实现线性查找
 * 
 * @author lenovo
 * 
 */
public class LSearch {

	public static int[] Data = { 12, 76, 29, 22, 15, 62, 29, 58, 35, 67, 58,
			33, 28, 89, 90, 28, 64, 48, 20, 77 }; // 输入数据数组

	public static int count = 1; // 查找次数计数变量

	public static void main(String[] args) {
		int KeyValue = 22;
		// 调用线性查找
		if (Linear_Search((int) KeyValue)) {
			// 输出查找次数
			System.out.println("");
			System.out.println("Search Time = " + (int) count);
		} else {
			// 输出没有找到数据
			System.out.println("");
			System.out.println("No Found!!");
		}

	}

	// 顺序查找
	public static boolean Linear_Search(int Key) {
		int i; // 数据索引计数变量

		for (i = 0; i < 20; i++) {
			// 输出数据
			System.out.print("[" + (int) Data[i] + "]");
			// 查找到数据时
			if ((int) Key == (int) Data[i])
				return true; // 传回true
			count++; // 计数器递增
		}
		return false; // 传回false
	}
}

 

 

折半查找

package com.search;

/**
 * 折半查找
 * 优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，
 * 且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。
 * 
 * 算法描述
 * 首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；
 * 否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，
 * 否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。
 * 
 * @author lenovo
 * 
 */
public class BSearch {

	public static int Max = 20;
	public static int[] Data = { 12, 16, 19, 22, 25, 32, 39, 48, 55, 57, 58,
			63, 68, 69, 70, 78, 84, 88, 90, 97 }; // 数据数组
	public static int Counter = 1; // 计数器

	// ---------------------------------------------------
	// 折半查找法
	// ---------------------------------------------------
	public static boolean BinarySearch(int KeyValue) {
		int Left; // 左边界变量
		int Right; // 右边界变量
		int Middle; // 中位数变量

		Left = 0;
		Right = Max - 1;

		while (Left <= Right) {
			Middle = (Left + Right) / 2;
			if (KeyValue < Data[Middle]) // 欲查找值较小
				Right = Middle - 1; // 查找前半段
			// 欲查找值较大
			else if (KeyValue > Data[Middle])
				Left = Middle + 1; // 查找后半段
			// 查找到数据
			else if (KeyValue == Data[Middle]) {
				System.out.println("Data[" + Middle + "] = " + Data[Middle]);
				return true;
			}
			Counter++;
		}
		return false;
	}

	public static void main(String args[]) {
		int KeyValue = 22;
		// 调用折半查找
		if (BinarySearch((int) KeyValue)) {
			// 输出查找次数
			System.out.println("");
			System.out.println("Search Time = " + (int) Counter);
		} else {
			// 输出没有找到数据
			System.out.println("");
			System.out.println("No Found!!");
		}
	}

}