- 二分法查找是建立在已经排序的基础之上
- 查询元素有重复则取重复数据最大下标
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;
}
}
网友评论