二分法查找
二分法查找原理
使用二分法查找时需要以下两个条件:
没有重复元素
已经排好顺序
假设给定一组排好序且没有重复元素的数字,要从这些数字中快速找到x所在的位置,可以从这组数字的中间位置开始找,如果当前值与x相等,则查找成功,如果小于x则从后半段的中间位置继续找,如果大于x则从前半段的中间位置继续寻找,直到找到x所在的位置
例如一个数组里面的元素有:1,5,8,15,18,23,30
快速找到23对应的下标值
第一次:取得数组的中间位置的值15,15小于23,所以继续从后半段开始找,后半段的元素是18,23,30
第二次:取得数组后半段元素中间位置的值23,23等于23,即找到23对应的下标值5
代码实现
public class MyArrays{
publicstaticvoidmain(String[] args){
int[] a = {1,5,8,15,18,23,30};
int destElement = 23;
//要求从a数组中查找23这个元素的下标int index = binarySearch(a,destElement);
//如果找到则返回元素的下标,如果找不到统一返回 -1System.out.println((index==-1)? destElement + "元素不存在!":destElement + "在数组中的下标是:" + index);
}
//二分法查找的核心算法publicstaticintbinarySearch(int[] a,intdestElement){
int begin = 0;
int end = a.length-1;
while(begin <= end){
int middle = (begin + end)/2;
if(a[middle]==destElement){
return middle;
}elseif(a[middle]>destElement){
end = middle - 1;
}elseif(a[middle] < destElement){
begin = middle + 1;
}
}
return -1;
}
【二分法查找】}
推荐阅读
- EffectiveObjective-C2.0|EffectiveObjective-C2.0 笔记 - 第二部分
- 遇到一哭二闹三打滚的孩子,怎么办┃山伯教育
- 赢在人生六项精进二阶Day3复盘
- 2019年12月24日
- 陇上秋二|陇上秋二 罗敷媚
- 一百二十三夜,请嫁给我
- 迷失的世界(二十七)
- 我要我们在一起(二)
- 基于|基于 antd 风格的 element-table + pagination 的二次封装
- (二)ES6第一节变量(let|(二)ES6第一节变量(let,const)