package pers.ly.javase.algorithm;

import java.util.Arrays;

/**

* 二分法查找

* @author: Lu Yang

* @date: 2019-01-23 10:50:37

*

*/

public class BinarySearch {

public static void main(String[] args) {

Integer[] arr = {10,50,30,40,10,80,90,70,60,40,100,10};

// 數組排序 -> 二分法必要條件

Arrays.sort(arr);

System.out.println(Arrays.toString(arr));

System.out.println(binarySearch(arr,50));

}

/**

*

* @author: Lu Yang

* @date: 2019-01-23 11:44:01

* @param arr 數組

* @param value 數組元素值

* @return

*

*/

public static Integer binarySearch(Integer[] arr, Integer value) {

// 定義數組開始位置

Integer start = 0;

// 定義數組結束位置(arr.length是計算數組從1開始的總長度,arr.length-1計算數組從0開始的總長度)

Integer end = arr.length - 1;

// 開始位置 <= 結束位置

while (start <= end) {

// 定義數組的中心位置(開始位置+結束位置)/2

Integer mid = (start + end) / 2;

// 判斷數組mid位置值(當前數據中間位置值)是否小于傳過來的值

if (arr[mid] < value)

// 如果小于傳過來的值,數組開始位置則定義中間位置下標+1

start = mid + 1;

// 判斷數組mid位置值(當前數據中間位置值)是否大于傳過來的值

if (arr[mid] > value)

// 如果大于傳過來的值,數組結束位置則定義中間位置下標-1

end = mid - 1;

if (arr[mid] == value)

return mid;

}

return -1;

}

}