search.java

来自「这里面包含有栈」· Java 代码 · 共 91 行

package org.huhuiyu.datastructures;

import java.util.Scanner;

public class Search {
	/**
	 * 查找数据key在datas数组中的下标，找不到就返回-1
	 * 
	 * @param datas
	 * @param key
	 * @return 数据key在datas数组中的下标，找不到就返回-1
	 */
	public static int search(int[] datas, int key) {
		for (int i = 0; i < datas.length; i++) {
			if (datas[i] == key) {
				return i;
			}
		}
		return -1;
	}

	/**
	 * 对分查找数据key在datas数组中的下标，找不到就返回-1
	 * 
	 * @param datas
	 * @param key
	 * @return 数据key在datas数组中的下标，找不到就返回-1
	 */
	public static int binarySearch(int[] datas, int key) {
		int start = 0;
		int end = datas.length - 1;
		int mid;
		while (start <= end) {
			mid = (start + end) / 2;
			if (key > datas[mid]) {
				start = mid + 1;
			}
			else if (key < datas[mid]) {
				end = mid - 1;
			}
			else if (key == datas[mid]) {
				return mid;
			}
		}
		return -1;
	}

	/**
	 * 对分查找数据key在datas数组中的下标，找不到就返回-1
	 * 
	 * @param start
	 *            查找的起始下标
	 * @param end
	 *            查找的结束下标
	 * @param datas
	 * @param key
	 * @return
	 */
	public static int binarySearch(int start, int end, int[] datas, int key) {
		if (start <= end) {
			int mid = (start + end) / 2;
			if (key > datas[mid]) {
				return binarySearch(mid + 1, end, datas, key);
			}
			else if (key < datas[mid]) {
				return binarySearch(start, mid - 1, datas, key);
			}
			else if (key == datas[mid]) {
				return mid;
			}
		}
		return -1;
	}

	public static void main(String[] args) {
		int[] datas = Common.getRandomData(5);
		Common.showArray(datas);
		Scanner scanner = new Scanner(System.in);
		System.out.printf("请输入要查找的数(int)：");
		int key = scanner.nextInt();
		int index = Search.search(datas, key);
		System.out.printf("%d在数组中的下标是：%d%n", key, index);
		Sort.selectionSort(datas);
		Common.showArray(datas);
		index = Search.binarySearch(datas, key);
		System.out.printf("%d在数组中的下标是：%d%n", key, index);
		index = Search.binarySearch(0, datas.length - 1, datas, key);
		System.out.printf("%d在数组中的下标是：%d%n", key, index);
	}
}