数组查值

问题描述:{4,5,7,8,1,2} 找值为K的元素。

两种做法，一种常规的稍好于直接查找，另一种为二分o（lgn）

import java.util.Arrays;

public class FindK {

	public static void main(String[] args) {
		int[] a = { 4, 5, 7, 8, 1, 2 };
		int[] b = { 1, 2, 3, 4, 5 };
		System.out.println(findK0(a, 5));
		 System.out.println(findK(a,5));
		// System.out.println(findK(a,6));
	}
	/**
	 * 折半
	 * @param a
	 * @param k
	 * @return
	 */
	public static int findK0(int[] a, int k) {
		if (a == null)
			return -1;
		int l = 0, r = a.length;
		while (l + 1 < r) {
			int m = l + (r - l) / 2;
			if (a[m] >= a[l]) {
				if (k < a[m]) {
					if (k >= a[l])
						r = m;
					else
						l = m;
				} else {
					l = m;
				}
			} else {
				if (k >= a[m]) {
					if (k <= a[r - 1])
						l = m;
					else
						r = m;
				} else {
					r = m;
				}
			}
		}
		return a[l] == k ? l : -1;
	}

	public static boolean findK(int[] a, int k) {
		for (int i = 0; i < a.length; i++) {
			if (a[i] == k)
				return true;
			else if (a[i] > k && i == 0) {
				for (int j = a.length; j > i; i--) {
					if (a[j] < a[i]) {
						if (a[j] == k)
							return true;
						else if (a[j] < k)
							return false;
						else if (a[j - 1] > a[j])
							return false;
						else
							continue;
					} else
						return false;
				}
			} else {
				if (a[i] < a[i + 1] && a[i] < k)
					continue;
				else
					return false;
			}
		}
		return false;
	}

}