アルゴリズム学習(二):二分法アルゴリズム

二分法アルゴリズムはよく言われているが,解釈しない.
注意点:

配列は、まず

に整列しなければならない.

整数相殺は四捨五入ではなく、余分な小数部を直接取り除くのでlow=mid+1である.high = mid-1

package com.xmq.algorithm;
import edu.princeton.cs.algs4.StdOut;

/**
 * Created by xmq on 2017/10/12.
 *        
 *    ： 1.        
 *         2.           ，           ，    low = mid+1   ; high =  mid-1
 */

public class BinarySearch {
    public static void main(String[] args) {
        int[] numbers = {3, 5, 6, 7, 8, 10, 11, 13, 14, 15};     //         
        StdOut.print(rank(3,numbers));
    }

    public static int rank(int target, int[] array){
        int low = 0;
        int high = array.length -1;

        for (int i = 0; i < array.length; i++) {
            int mid = low + ( high -low )/2; //            （      ）   3／2 =1
            if (target > array[mid]) {
                low = mid +1;
            } else if (target < array[mid]) {
                high = mid -1;
            } else {
                return mid;
            }
        }
        return -1;
    }

}