二分查找算法是在有序数组中用到的较为频繁的一种算法。

在未接触二分查找算法时,最通用的一种做法是,对数组进行遍历,跟每个元素进行比较,其时间复杂度为O(n),但二分查找算法则更优,因为其查找时间复杂度为O(log2 n)。

比如数组{0,1,2,3,4,5,6,7,8 9},查找元素6,用二分查找的算法执行的话,其顺序为:

1.第一步查找中间元素,即4,由于4<6,则6必然在4之后的数组元素中,那么就在{5,6,7,8,9}中查找,

2.寻找{5,6,7,8,9}的中位数,为7,7>6,则6应该在7左边的数组元素中,那么只剩下{5,6},按此类推就可以找到了。

二分查找算法就是不断将数组进行对半分割,每次拿中间元素和goal进行比较。

public class BinarySearchDemo {
/**
* 非递归方法,利用while循环
*
* @param arr
* @param des
* @return
*/
public static int binarySearch(int[] arr, int des) {
int low = 0;
int high = arr.length - 1;
while (low <= high) {
// 使用 (low + high) / 2,如果low和high的和大于Integer.MAX_VALUE(在java中是2 23 -1),计算就会发生溢出,使(low + high)成为一个负数,然后被2除,结果当然仍是负数。
// int middle = (low + high) / 2;
int middle = low + (high - low) / 2;
if (arr[middle] == des) {
return middle;
} else if (arr[middle] < des) {
low = middle + 1;
} else {
high = middle - 1;
}
}
return -1;
} /**
* 递归查找
*
* @param arr
* @param des
* @param low
* @param high
* @return
*/
public static int binarySearch(int[] arr, int des, int low, int high) {
// int middle = (low + high) / 2;
int middle = low + (high - low) / 2;
if (des < arr[low] || des > arr[high] || low > high) {
return -1;
}
if (arr[middle] < des) {
return binarySearch(arr, des, middle + 1, high);
} else if (arr[middle] > des) {
return binarySearch(arr, des, low, middle - 1);
} else {
return middle;
}
} public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 11, 15, 17};
int des = 15;
System.out.println("所查找元素在数组中的下标为:" + binarySearch(arr, des));
System.out.println("所查找元素在数组中的下标为:" + binarySearch(arr, des, 0, 10));
}
}

最新文章

  1. VIM配置与管理
  2. 用java页面下载图片
  3. Kafka/Metaq设计思想学习笔记 转
  4. css中的id和css的区别
  5. userdate和table类型的效率对比
  6. CLRS:Insert sort in in c
  7. C++之友元函数
  8. javascript面向对象创建高级 Web 应用程序
  9. NG2入门 - 根模块
  10. 一、java自带的观察者模式
  11. 杭电2000——ASCII码排序
  12. 打造适合你的ABP(1)---- 完善日志系统
  13. keil在线烧录突然提示 No target connected #
  14. 提供HTML5播放RTSP流 提供微信播放RTSP流 HTML5支持rtsp web播放rtsp,微信支持rtsp
  15. CentOS 7 nginx+tomcat9 session处理方案之session保持
  16. JS实时获取输入框中的值
  17. vscode已有64位版本。
  18. xe5 android 控制蓝牙[转]
  19. hdu 5194 组合数学or暴力
  20. .net core中的System.Buffers名字空间

热门文章

  1. C#加密方法汇总(SHA1加密字符串,MD5加密字符串,可逆加密等)
  2. 二维数组malloc
  3. Data Guard Wait Events
  4. MyBatis:4
  5. 使用GAN 进行异常检测——anoGAN,TODO,待用于安全分析实验
  6. app.jsNodejs启动测试服务
  7. Tarjan 算法求强联通分量
  8. jsp jsp的基本语法
  9. linux processes identifiers
  10. UAC 注册表 WIN64 OS 运行时主题