java实现的二分查找算法（包含重复数据）
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了java实现的二分查找算法（包含重复数据），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2698字，纯文字阅读大概需要4分钟。
内容图文
二分查找算法：
- 待查找的数组是有序的；
- 查找中间数组，为了拆分待查找的数组；
- 需要得到起止下标；
- 本文采用了递归方法（如果在第一次比较就已经找到了数组，将不需要进行递归）；
- 递归是为了更快的找到数据；
- 程序里面的查分数组，只是逻辑上的查分，实际的输入数组还是完整的，在重复元素问题上，更能体现。
在这里插入代码片
package SearchTest;
import java.util.ArrayList;
import java.util.List;
/**
*
- @author Administrator
*/
public class BinarySearchTest {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] arr = { 1, 1, 1, 1, 1, 11 };// 有序数列
List<Integer> tmp = binarysearch2(arr, 0, arr.length - 1, 1);
System.out.println(tmp);
}
// 编写二分查找方法，采用递归方式，数组中无重复数据的情况下
/**
*
* @param arr查找数组
* @param left左起始下标值
* @param right右边结束下标值
* @param searchVal待查找的数据
* @return
*/
public static int binarysearch(int[] arr, int left, int right, int searchVal) {
if (left > right) {
return -1;
}
int mid = (left + right) / 2;// 数组中线数组的下标
int midVal = arr[mid];// 找到对于数组中间数据下标的数据
if (searchVal < midVal) {// 带比较值小于中间值，下一步需要向左递归
return binarysearch(arr, left, mid - 1, searchVal);
} else if (searchVal > midVal) {// 带比较值大于中间值，下一步需要向右递归
return binarysearch(arr, mid + 1, right, searchVal);
} else {// 如果两值相等，则就是中间值，需要返回中间值下标
return mid;
}
}
// 对于数组里面有重复的数据的情况下
/**
*
* @param arr
* @param left
* @param right
* @param searchVal
* @return返回一个列表，里面存储了查找的下标的结果，里面的下标可能不是按照下标从小到大的顺序存放的，而是根据比较的顺序存放的
*/
public static ArrayList<Integer> binarysearch2(int[] arr, int left, int right, int searchVal) {
if (left > right) {
return new ArrayList<Integer>();
}
int mid = (left + right) / 2;// 数组中线数组的下标
int midVal = arr[mid];// 找到对于数组中间数据下标的数据
if (searchVal < midVal) {// 比较值小于中间值，下一步需要向左递归
return binarysearch2(arr, left, mid - 1, searchVal);
} else if (searchVal > midVal) {// 比较值大于中间值，下一步需要向右递归
return binarysearch2(arr, mid + 1, right, searchVal);
} else {// 如果两值相等，则就是中间值，需要返回中间值下标
// 如果在第一次比较久发现相等的数，将不会进入递归
ArrayList<Integer> list = new ArrayList<Integer>();
int tmp1 = mid - 1;
while (true) {// 向左比较,因为是有序数列，所以需要从Mid下标的左右继续查找
if (tmp1 < 0 || arr[tmp1] != searchVal) {
break;
}
list.add(tmp1);//将遍历的数据下标加入到列表中
tmp1 -= 1;//减1，继续向左比较
}
list.add(mid);// 将中间添加
int tmp = mid + 1;
while (true) {// 向右比较
if (tmp > arr.length - 1 || arr[tmp] != searchVal) {
break;
}
list.add(tmp);
tmp += 1;//加1，继续向右比较
}
return list;
}
}
}
智张 发布了2 篇原创文章 · 获赞 0 · 访问量 29 私信 关注内容总结
以上是互联网集市为您收集整理的java实现的二分查找算法（包含重复数据）全部内容，希望文章能够帮你解决java实现的二分查找算法（包含重复数据）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源：【匿名】