读书人

2分搜寻法(搜寻原则的代表)

发布时间: 2012-12-26 14:39:29 作者: rapoo

二分搜寻法(搜寻原则的代表)

如果搜的列已有排序,量利用它已排序的特性,以少搜比的次,是搜的基本原,二分搜法是基本原的代表。
解法
在二分搜法中,列的中始搜,如果小於我所搜的,由於列已排序,左的一定都小於要搜的象,所以需浪在左的;如果搜的大於所搜的象,右的需再搜,直接搜左的。

所以在二分搜法中,列不的分部份,每次分割的部份中取中比,例如要搜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 : "找不到值");     }} 

读书人网 >编程

热点推荐