二分查找

二分查找的思想其實是為了減少搜索范圍，每次縮減一半，這樣就可以快速找到對象。

1.二分查找的對象

二分查找的對象是有序的數(shù)組。如果一個數(shù)組沒有按順序排好則無法應用二分查找。

2.二分查找用例

package com.mingguo.zjut.main;

public class BinarySearch {

    public static int rank(int key,int a[]){
        int L = 0;
        int R = a.length - 1;
        while(L<=R){
            int mid = L +(R-L)/2;
            if(a[mid]==key){
                return mid;
            }else if(a[mid] > key){
                R = mid - 1;
            }else if(a[mid] < key){
                L = mid + 1;
            }
        }
        return -1;
    }
    public static void main(String[] args) {
        int newArray [] = {
            1,2,3,4,5,6,7,8
        };
        System.out.println(rank(1,newArray));
    }

}

3.二分查找過程

上述二分查找代碼是用rank()函數(shù)實現(xiàn)的，該函數(shù)接受一個整數(shù)和一個已經(jīng)有序的int數(shù)組作為參數(shù)。如果該鍵存在于數(shù)組中則返回他的索引，否則返回-1。該算法使用了兩個變量L和R，并保證如果該鍵存在于數(shù)組中，則它一定在a[L..R]中，然后方法進入下一次的循環(huán)，不斷的將數(shù)組的中間鍵（索引為mid）和被查找的鍵比較。如果查找的鍵等于a[mid],返回mid；否則算法就會將范圍縮小為原來的一半，如果被查找的鍵小于a[mid]就繼續(xù)在左半邊找，如果被查找的鍵大于a[mid]就繼續(xù)在右半邊找。算法找到該鍵或者查找范圍為空（L>R）時該過程結束。二分查找之所以快是因為它只需檢查很少幾個條目（相對于數(shù)組的大?。┚湍苷业侥繕嗽兀ɑ蛘叽_認目標元素不存在）。