二分搜寻法(搜寻原则的代表)
明
如果搜的列已有排序,量利用它已排序的特性,以少搜比的次,是搜的基本原,二分搜法是基本原的代表。
解法
在二分搜法中,列的中始搜,如果小於我所搜的,由於列已排序,左的一定都小於要搜的象,所以需浪在左的;如果搜的大於所搜的象,右的需再搜,直接搜左的。
所以在二分搜法中,列不的分部份,每次分割的部份中取中比,例如要搜92於以下的列,首先中索引(0+9)/2 = 4(索引由0始):
[3 24 57 57 67 68 83 90 92 95]
由於67小於92,所以搜右的列:
3 24 57 57 67 [68 83 90 92 95]
由於90小於92,再搜右的列,次就找到所要的了:
3 24 57 57 67 68 83 90 [92 95]
public class Search { public static int binary(int[] number, int des) { int low = 0; int upper = number.length - 1; while(low <= upper) { int mid = (low+upper) / 2; if(number[mid] < des) low = mid+1; else if(number[mid] > des) upper = mid - 1; else return mid; } return -1; } public static void main(String[] args) { int[] number = {1, 2, 3, 4, 6, 7, 8}; int find = Search.binary(number, 2); System.out.println(find >= 0 ? "找到值於索引" + find : "找不到值"); }}