java二分查找算法代码 java二分法查找算法

关于java的binarySearch（）方法

结果是-6的原因是在子串[2,3,4,5,6]中并未找到8这个数字。然后我们来看一下binrySearch的源码

成都创新互联2013年至今，是专业互联网技术服务公司，拥有项目成都做网站、成都网站设计网站策划，项目实施与项目整合能力。我们以让每一个梦想脱颖而出为使命，1280元福安做网站,已为上家服务,为福安各地企业和个人服务,联系电话:028-86922220

public static int binarySearch(int[] a, int fromIndex, int toIndex,

int key) {

rangeCheck(a.length, fromIndex, toIndex);

return binarySearch0(a, fromIndex, toIndex, key);

}

private static int binarySearch0(int[] a, int fromIndex, int toIndex,

int key) {

int low = fromIndex;

int high = toIndex - 1;

while (low = high) {

int mid = (low + high) 1;

int midVal = a[mid];

if (midVal key)

low = mid + 1;

else if (midVal key)

high = mid - 1;

else

return mid; // key found

}

return -(low + 1);  // key not found.

}

可以从源码中看到，真正的二分查找是在binarySearch0方法中进行的。每次循环都会计算出本轮的中间位置mid，以及获取中间值midVal。当中间值小于key时，说明要找的值在右半边，low等于mid+1，当中间值大于key说明在左半边，high=mid-1,找到了然后开始下一轮。当等于时也就是找到了目标值，直接返回位置mid。如果最后找不到目标值，则返回-(low+1)。

再来看看具体问题的执行：

第一轮算出的mid是(1+5) 1 =2，midValue=3 8 ,low=3；

进入第二轮mid为（3+5）1  =3,midValue=4 8 ,low=4；

进入第三轮mid为（4+5）1 = 4，midValue=5 8,low=5; 此时low==high跳出while循环 返回-（5+1）即-6.

拓展知识

二分查找的流程如下图：

java泛型 二分查找

以下代码是关于对象的 二分查找 的例子，已经测试通过，执行即可。

Student 是基本比较对象类

Dichotomy 是二分法执行类

Test 是测试类

package com.dichotomy;

public class Student implements ComparableStudent {

private int id;

private String name;

private String idCard;

private String sex;

private String mobile;

public int getId() {

return id;

}

public void setId(int id) {

this.id = id;

}

public String getName() {

return name;

}

public void setName(String name) {

this.name = name;

}

public String getIdCard() {

return idCard;

}

public void setIdCard(String idCard) {

this.idCard = idCard;

}

public String getSex() {

return sex;

}

public void setSex(String sex) {

this.sex = sex;

}

public String getMobile() {

return mobile;

}

public void setMobile(String mobile) {

this.mobile = mobile;

}

/**

* 排序控制

* @param o1 Student

* @param o2 Student

* @return int 返回 -1 向前移动, 1 向后移动, 0 不移动

* 这个方法需要自己进行调整，排序比较和二分查找时均使用此方法进行位置调整

* 比较时使用的key自己可以进行修改，不过要保证唯一性，否则查询出来的值会不准确

*/

public int compareTo(Student o) {

//不同的执行次序决定排序和查找次序不同,可以同下面的调换一下

if(this.getId() o.getId()){

return -1;

} else if(this.getId() == o.getId()){

;

} else {

return 1;

}

//不同的执行次序决定排序和查找次序不同

int c = this.getIdCard().compareTo(o.getIdCard());

if(c != 0){

return c;

}

//不同的执行次序决定排序和查找次序不同

int n = this.getName().compareTo(o.getName());

if(n != 0){

return n;

}

return 0;

}

public String toString(){

StringBuffer sb = new StringBuffer();

sb.append(this.getId()).append("\t");

sb.append(this.getName()).append("\t");

sb.append(this.getIdCard()).append("\t");

sb.append(this.getMobile()).append("\t");

sb.append(this.getSex());

return sb.toString();

}

}

什么叫java中的二分查找法

1、算法概念。

二分查找算法也称为折半搜索、二分搜索，是一种在有序数组中查找某一特定元素的搜索算法。请注意这种算法是建立在有序数组基础上的。

2、算法思想。

①搜素过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜素过程结束；

②如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。

③如果在某一步骤数组为空，则代表找不到。

这种搜索算法每一次比较都使搜索范围缩小一半。

3、实现思路。

①找出位于数组中间的值，并存放在一个变量中（为了下面的说明，变量暂时命名为temp）；

②需要找到的key和temp进行比较；

③如果key值大于temp，则把数组中间位置作为下一次计算的起点；重复① ②。

④如果key值小于temp，则把数组中间位置作为下一次计算的终点；重复① ② ③。

⑤如果key值等于temp，则返回数组下标，完成查找。

4、实现代码。

/**

* description : 二分查找。

* @param array 需要查找的有序数组

* @param from 起始下标

* @param to 终止下标

* @param key 需要查找的关键字

* @return

*/

public static E extends ComparableE int binarySearch(E[] array, int from, int to, E key) throws Exception {

if (from  0 || to  0) {

throw new IllegalArgumentException("params from  length must larger than 0 .");

}

if (from = to) {

int middle = (from  1) + (to  1); // 右移即除2

E temp = array[middle];

if (temp.compareTo(key)  0) {

to = middle - 1;

} else if (temp.compareTo(key)  0) {

from = middle + 1;

} else {

return middle;

}

}

return binarySearch(array, from, to, key);

}