考察點(diǎn)

算法二分搜索

知識(shí)點(diǎn)

二分搜索算法是針對(duì)排序的數(shù)組，先找到中間元素，如果待查找元素比中間元素大，說明待查
找元素肯定不在左邊那片區(qū)域內(nèi)，如果待查找元素比中間元素小，說明待查找元素肯定不在右
邊那片區(qū)域內(nèi)，反復(fù)進(jìn)行該過程直到找到元素為止對(duì)于搜索而言，降低復(fù)雜度的唯一方式就是
每一次輪詢以后能縮小搜索范圍或者過濾掉更多的不可能元素，我們最普通的遍歷數(shù)組的方式
，每輪詢完一次只能過濾掉一個(gè)元素。而二分搜索每輪詢完一次可以過濾掉一半的元素，因此
這就是它非常高效的原因(log(n))

題目

分析
首先一定要記住只要看到排序數(shù)組的查找，思維一定要往二分法上靠，然后再思考清楚如何利用二分法。而如何利用二分法一定要仔細(xì)分析所給的數(shù)組的特點(diǎn)：遞增數(shù)組且最開始的若干元素搬到數(shù)組的末尾，相當(dāng)于該數(shù)組由倆個(gè)遞增小數(shù)組構(gòu)成，前面的數(shù)組元素肯定大于等于后面的數(shù)組元素，且最小值肯定是第二個(gè)小數(shù)組的第一個(gè)元素。二分法需要首尾倆個(gè)指針以及中間元素，可以肯定的是如果中間元素比最左邊的值大那說明最小值肯定在右邊(左邊的小遞增數(shù)組特性)，如果中間元素比最右邊的值小那說明最小值肯定在左邊(右邊的小遞增數(shù)組特性)，到這一步的時(shí)候就需要拿數(shù)字舉例一下看到底應(yīng)該怎么找到最小值，最終舉例完以后會(huì)發(fā)現(xiàn)按照上面的思路最終左邊的指針和右邊的指針相差1的時(shí)候，右邊的指針指向的就是最小的元素(在解題沒有思路的時(shí)候拿實(shí)際數(shù)據(jù)算一下然后找出其中的規(guī)律，我們的算法說白了就是把這個(gè)規(guī)律用程序表達(dá)出來)。最后考慮一些異常的情況：中間元素比最左邊的值大的時(shí)候最小值肯定在右邊嗎？不一定，考慮數(shù)組{1,0,1,1,1}的情況，因此當(dāng)最左邊元素和中間元素以及最右邊元素值相同的時(shí)候，就不能再使用二分法進(jìn)行查找了
(末尾附上二分查找代碼)文章來源地址http://www.zghlxwxcb.cn/news/detail-820916.html

public class Eight {
	public static void main(String[] args) {
		int[] arr = {3,4,5,1,2};
		System.out.println(findMin(arr));
		int[] brr = {1,0,1,1,1};
		System.out.println(findMin(brr));
		int[] crr = {1,1,1,0,1};
		System.out.println(findMin(crr));
		int[] drr = {5,4,3,2,1};
		System.out.println(findMin(drr));
	}
	public static int findMin(int[] arr) {
		if (arr.length <= 0) {
			throw new Error("input error");
		}
		int start = 0;
		int end = arr.length - 1;
		if (arr[start] < arr[end]) {
			return arr[start];
		}
		while(arr[start] >= arr[end]) {
			if (start + 1 == end) {
				return arr[end];
			}
			int mid = (start + end) / 2;
			if (arr[start] == arr[mid] && arr[end] == arr[mid]) {
				int val = arr[start];
				for (int idx = start + 1;idx <= end;idx++) {
					if (val > arr[idx]) {
						val = arr[idx];
					}
				}
				return val;
			}
			if (arr[mid] >= arr[start]) {
				start = mid;
			} else if (arr[mid] <= arr[end]) {
				end = mid;
			} else {
				break;
			}
		}
		throw new Error("input error");
	}
}
//附上二分法查找
public class Erfen {
	public static void main(String[] args) {
		int[] arr = {1,2,3,4,11,17,18};
		System.out.println(erfen(arr,12));
		System.out.println(erfen(arr,18));
		System.out.println(erfen(arr,1));
		System.out.println(erfen(arr,11));

	}
	public static int erfen(int[] arr,int val) {
		int start = 0;
		int end = arr.length - 1;
		while(start <= end) {
			int mid = (start + end) / 2;
			if (arr[mid] == val) {
				return mid;
			} else if (arr[mid] < val) {
				start = mid + 1;
			} else {
				end = mid - 1;
			}
		}
		return -1;
	}
}

到了這里，關(guān)于劍指offer面試題8 旋轉(zhuǎn)數(shù)組的最小數(shù)字的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！