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);
	}
}