算法-二分查找（java）

算法-二分查找（java）

        又叫折半查找，要求待查找的序列有序。每次取中间位置的值与待查关键字比较，如果中间位置的值比待查关键字大，则在前半部分循环这个查找的过程，如果中间位置的值比待查关键字小，则在后半部分循环这个查找的过程。直到查找到了为止，否则序列中没有待查的关键字。

package org.example.algorithm;

import java.util.Arrays;

public class BisSearch {

    public static void main(String[] args) {
        int[] a = {2, 3, 5, 6, 7, 8, 9};
        Arrays.sort(a);
        System.out.println(new BisSearch().biSearch(a, 6));
    }

    // 7个数字：2,3,5,6,7,8,9
    int biSearch(int[] arr, int a) {
        int low = 0;
        int height = arr.length - 1;
        int pos = -1;
        while (low <= height) {
            int mid = (low + height) / 2;
            if (arr[mid] == a) {
                return pos=mid;
            } else if (a > arr[mid]) {
                low = mid + 1;
            } else if (a < arr[mid]) {
                height = mid - 1;
            }
        }
        return pos;
    }
}

mid = (low + height) / 2;  中间值的计算公式由来

譬如下面7个元素的数组，数组下标分别 0,1,2,3,4,5,6

数组元素：2, 3, 5, 6, 7, 8, 9  我们要找到7

第一次：low=0，heigth= len-1 =6

mid = heigth/2 =(low+heigth)/2 = (0+6)/2=3

第二次：7比mid[3] 大，落在右边

low = mid+1=4，heigth=6 不变

mid = (heigth-low)/2 +low = (low+height)/2 = (4+6)/2=5