首页 > 代码库 > 关于二分查找中的一些问题
关于二分查找中的一些问题
相信对于学习编程每一个同学来说，肯定都知道二分查找算法，并且写过相应的测试代码，那么我们先来说一下二分查找的的优缺点吧。
这大家都很清楚，优点呢就是二分查找是折半查找，每次查找都可以排除一半的数据，这应用在一个大数据量的查找中，效率是非常高的。当然了，缺点也很明显，就是二分查找的前提是，查找的数据一定是经过排序的，无论是升序还是降序，这会打乱原先的数据的位置。所以在实际情况中，还请大家仔细考虑，是否需要进行二分查找。
话不多说，我们直接上代码。
public class Main{
public static int getPos(int[] A, int n, int val) {
return indexOf(A,val,n);
}
public static int indexOf(int[] a,int val,int n){
int low=0;
int high = n-1;
while(low < high) {
int middle = (low+high)/2;
if(val > a[middle]) {
low=middle+1;
}else if (val == a[middle]) {
//若查找到，直接返回元素的索引
return middle;
} else {
high=middle-1;
}
}
//未找到，返回-1
return -1;
}
public static void main(String[] args)
{
int[] a={1,4,7,9,15}; //数组必须是经过排序的
int n=a.length;
int val=1;
System.out.println(getPos(a, n, val));
}
}
相信大家对这种二分查找应该很熟悉，当然输出结果为0.
现在我们来考虑另外一种情况，就是元素不是递增或者递减的，而是非递增或者非递减的情况，什么意思呢，就是说数组中包含相同的元素，这种情况下我们想的是返回元素第一次在数组中出现的位置，那么结果是这样吗？让我们测试一下。
修改数组元素为[1,3,3,4,5]，查找元素为3的索引
结果为：
。结果并不和我们想的一样，首先我们来分析一下原因。折半查找首先会从中间元素开始查找，寻找特定的元素，所以靠近中间位置的元素首先会被找出来。所以现在看来，出现这个问题也不是很意外了，那我们应该怎么解决呢。
解决思路如下:当寻找出我们要的那个元素之后，应该继续向索引小的一方继续查找，若存在和当前值相等的元素，则返回索引值小的元素，若不存在，直接将当前索引值返回即可。思路很简单，关键在于代码实现。那么接下来，我们看代码。
public class Test6 { public static int getPos(int[] A, int n, int val) { return indexOf(A,val,n); } public static int indexOf(int[] a,int val,int n){ int low=0; int high = n-1; while(low < high) { int middle = (low+high)/2; if(val > a[middle]) { low=middle+1; }else if (val == a[middle]) { //主要就是改进这段代码 int temp=middle; //先判断索引值的目的是防止数组越界异常 while(temp > 0 && a[--temp] == val) { middle--; } return middle; } else { high=middle-1; } } //未找到，直接返回-1 return -1; } public static void main(String[] args) { int[] a={1,3,3,4,5}; //数组必须是经过排序的 System.out.println("数组元素为：[1,3,3,4,5]"); int n=a.length; int val=3; System.out.println("元素3的索引值："+getPos(a, n, val)); } } 运行结果为： 数组元素为：[1,3,3,4,5] 元素3的索引值：1
代码底部有运行结果，可以看出这个结果才是我们想要的。以上就是我关于二分查找的一些总结，希望对你们有帮助。
通过这个例子，我们可以总结出：解决问题的时候，一定要考虑清楚所有的细节，也是出现相等元素只是一个小问题，但就是这种小问题，有可能会困扰到我们，所以说一些细枝末节我们才不能放过。
关于二分查找中的一些问题