本文目录一览：
- 1、java泛型 二分查找
- 2、JAVA二分查找
- 3、用二分法查找（折半查找）java
- 4、用java写二分搜索，要求数组是由用户输入，再输入时，数组是无序的，要对数组进行从小到大的排序
- 5、JAVA 二分算法只能对数字进行查找吗
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二分查找
//*******二分查找，都注释了，复制所有代码，保存成QuickSortApp.java*************//
class ArrayIns
{
private long theArray[];
private int nElems;
//--------------------
public ArrayIns(int max){ //构造方法，初始化成员属性。
theArray = new long[max];
nElems = 0;
}
//-----------------------
public void insert(long value){ //insert方法用于给数组赋值，并用nElems记录数组元素的个数。
theArray[nElems] = value;
nElems++;
}
//----------------------------
public void display(){ //display方法用于显示数组的所有元素到控制台。
System.out.println("A= ");
for(int j=0;jnElems;j++)
System.out.print(theArray[j]+" ");
System.out.println("");
}
//------------------------------
public void quickSort(){ //ArrayIns对象调用quickSort方法可以为其成员属性theArray数组中的元素排序（从小到大）
recQuickSort(0,nElems-1); //调用recQuickSort方法开始排序，初始范围从第一个到最后一个开始。
}
//-------------------------------
private void recQuickSort(int left,int right){ //recQuickSort方法进行数组元素的排序。left,right表示排序的范围.
if(right-left = 0)
return; //如果right小于left,则第归返回。此处是第归的出口。
else {
long pivot = theArray[right]; //每次把排序范围中的最后一个数作为排序时的参照数。
int partition = partitionIt(left,right,pivot); //调用prititionIt方法，参数列表中指明排序的范围和参照数，并将方法的返回值赋给pritition变量(用来指明下一次排序时的范围。)
//System.out.print(" "+1); //数字1代表第一次第归的调用。
recQuickSort(left,partition-1); //第归调用本方法，排序右范围由partition-1来决定。
//System.out.print(" "+2); //数字2代表第二次第归的调用。
recQuickSort(partition+1,right); //第归调用本方法，排序左范围由partition-1来决定。
}
}
//-----------------------------------
private int partitionIt(int left,int right,long pivot){ //partitionIt方法完成left和right范围内元素间排序的具体过程。
int leftPtr = left-1; //leftPrt表示左标识位，从left-1开始。
int rightPtr = right; //rightPrt表示右表识位，到right。 while(true){//永真循环。
while(theArray[++leftPtr] pivot); // 空循环，从leftPrt开始往rightPrt方向开始找一个比pivot大的数,用leftPtr记录元素的位置。
while(rightPtr0 theArray[--rightPtr]pivot);//空循环，从rightPrt往leftPrt方向开始找一个比pivot小的数，用rightPrt记录元素的位置,并且rightPtr0会保证不会数组越界。
if(leftPtr = rightPtr) //永真循环的出口，表示本次排序结束。
break;//跳出循环。
else
swap(leftPtr,rightPtr);//将leftPtr和rightPtr所在位置的元素进行交换。
}
swap(leftPtr,right); //调用swap方法。
return leftPtr; //将leftPtr返回到本方法被调用的位置。用来指明下一次排序时的范围.
}
//---------------------------------------------
private void swap(int dex1,int dex2){ //swap方法用来将数组中的两个元素进行交换，dex1和dex2分别表示两个数组元素的位置。
long temp = theArray[dex1]; //temp变量作为两个数组元素交换时的临时中转变量。
theArray[dex1] = theArray[dex2];
theArray[dex2] = temp;
}
}//////////////////////////////////////////////////////////////////////////////////////class QuickSortApp
{
public static void main(String[] args)
{
int maxSize = 10; //定义变量maxSize，并赋初值10.
ArrayIns arr;
arr = new ArrayIns(maxSize);//创建ArrayIns类的对象arr for(int j=0;jmaxSize;j++){
long n = (int)(java.lang.Math.random()*99);//产生随机数。
arr.insert(n); //用insert方法为arr中的成员数组变量赋值。
}
arr.display(); //用display方法显示arr中成员变量数组中的所有元素。
arr.quickSort(); //用quickSort方法为arr成员变量数组中的元素按从小到大排序。
arr.display(); //显示。
}
}
用二分法查找（折半查找）java
二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。
二分查找优缺点
优点是比较次数少，查找速度快，平均性能好；
其缺点是要求待查表为有序表，且插入删除困难。
因此，折半查找方法适用于不经常变动而查找频繁的有序列表。
使用条件：查找序列是顺序结构，有序。
过程
首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。
利用循环的方式实现二分法查找
public class BinarySearch {
public static void main(String[] args) {
// 生成一个随机数组 int[] array = suiji();
// 对随机数组排序 Arrays.sort(array);
System.out.println("产生的随机数组为： " + Arrays.toString(array));
System.out.println("要进行查找的值： ");
Scanner input = new Scanner(System.in);
// 进行查找的目标值 int aim = input.nextInt();
// 使用二分法查找 int index = binarySearch(array, aim);
System.out.println("查找的值的索引位置： " + index);
}
/** * 生成一个随机数组 *
* @return 返回值，返回一个随机数组 */
private static int[] suiji() {
// random.nextInt(n)+m 返回m到m+n-1之间的随机数 int n = new Random().nextInt(6) + 5;
int[] array = new int[n];
// 循环遍历为数组赋值 for (int i = 0; i array.length; i++) {
array[i] = new Random().nextInt(100);
}
return array;
}
/** * 二分法查找 ---循环的方式实现 *
* @param array 要查找的数组 * @param aim 要查找的值 * @return 返回值，成功返回索引，失败返回-1 */
private static int binarySearch(int[] array, int aim) {
// 数组最小索引值 int left = 0;
// 数组最大索引值 int right = array.length - 1;
int mid;
while (left = right) {
mid = (left + right) / 2;
// 若查找数值比中间值小，则以整个查找范围的前半部分作为新的查找范围 if (aim array[mid]) {
right = mid - 1;
// 若查找数值比中间值大，则以整个查找范围的后半部分作为新的查找范围 } else if (aim array[mid]) {
left = mid + 1;
// 若查找数据与中间元素值正好相等，则放回中间元素值的索引 } else {
return mid;
}
}
return -1;
}}
运行结果演示：
由以上运行结果我们得知，如果要查找的数据在数组中存在，则输出该数据在数组中的索引；如果不存在则输出 -1 ，也就是打印 -1 则该数在数组中不存在，反之则存在。
四、利用递归的方式实现二分法查找
public class BinarySearch2 {
public static void main(String[] args) {
// 生成一个随机数组 int[] array = suiji();
// 对随机数组排序 Arrays.sort(array);
System.out.println("产生的随机数组为： " + Arrays.toString(array));
System.out.println("要进行查找的值： ");
Scanner input = new Scanner(System.in);
// 进行查找的目标值 int aim = input.nextInt();
// 使用二分法查找 int index = binarySearch(array, aim, 0, array.length - 1);
System.out.println("查找的值的索引位置： " + index);
}
/** * 生成一个随机数组 * * @return 返回值，返回一个随机数组 */
private static int[] suiji() {
// Random.nextInt(n)+m 返回m到m+n-1之间的随机数 int n = new Random().nextInt(6) + 5;
int[] array = new int[n];
// 循环遍历为数组赋值 for (int i = 0; i array.length; i++) {
array[i] = new Random().nextInt(100);
}
return array;
}
/** * 二分法查找 ---递归的方式 * * @param array 要查找的数组 * @param aim 要查找的值 * @param left 左边最小值 * @param right 右边最大值 * @return 返回值，成功返回索引，失败返回-1 */
private static int binarySearch(int[] array, int aim, int left, int right) {
if (aim array[left] || aim array[right]) {
return -1;
}
// 找中间值 int mid = (left + right) / 2;
if (array[mid] == aim) {
return mid;
} else if (array[mid] aim) {
//如果中间值大于要找的值则从左边一半继续递归 return binarySearch(array, aim, left, mid - 1);
} else {
//如果中间值小于要找的值则从右边一半继续递归 return binarySearch(array, aim, mid + 1, array.length-1);
}
}}
运行结果演示：
总结：
递归相较于循环，代码比较简洁，但是时间和空间消耗比较大，效率低。在实际的学习与工作中，根据情况选择使用。通常我们如果使用循环实现代码只要不是太繁琐都选择循环的方式实现~
用java写二分搜索，要求数组是由用户输入，再输入时，数组是无序的，要对数组进行从小到大的排序
二分查找又称折半查找，它是一种效率较高的查找方法。
【二分查找要求】：1.必须采用顺序存储结构 2.必须按关键字大小有序排列。
/**
* 二分查找又称折半查找，它是一种效率较高的查找方法。
【二分查找要求】：1.必须采用顺序存储结构 2.必须按关键字大小有序排列。
* @author Administrator
*
*/
public class BinarySearch {
public static void main(String[] args) {
int[] src = new int[] {1, 3, 5, 7, 8, 9};
System.out.println(binarySearch(src, 3));
System.out.println(binarySearch(src,3,0,src.length-1));
}
/**
* * 二分查找算法 * *
*
* @param srcArray
* 有序数组 *
* @param des
* 查找元素 *
* @return des的数组下标，没找到返回-1
*/
public static int binarySearch(int[] srcArray, int des){
int low = 0;
int high = srcArray.length-1;
while(low = high) {
int middle = (low + high)/2;
if(des == srcArray[middle]) {
return middle;
}else if(des srcArray[middle]) {
high = middle - 1;
}else {
low = middle + 1;
}
}
return -1;
}
/**
*二分查找特定整数在整型数组中的位置(递归)
*@paramdataset
*@paramdata
*@parambeginIndex
*@paramendIndex
*@returnindex
*/
public static int binarySearch(int[] dataset,int data,int beginIndex,int endIndex){
int midIndex = (beginIndex+endIndex)/2;
if(data dataset[beginIndex]||datadataset[endIndex]||beginIndexendIndex){
return -1;
}
if(data dataset[midIndex]){
return binarySearch(dataset,data,beginIndex,midIndex-1);
}else if(datadataset[midIndex]){
return binarySearch(dataset,data,midIndex+1,endIndex);
}else {
return midIndex;
}
}
}
JAVA 二分算法只能对数字进行查找吗
2分法查找，前提是要有序，要排序，必然要比较大小，所以只要一个类它实现了Comparable接口的compareTo(T o)方法（Comparable在java.lang包中）或是实现一个比较器对象接口Comparator(Comparator在java.util包)，都可以进行比较了。不管是String型,计本数据类型,还是其他什么的，都可以用2分发查找了。给你看看API
java．util．Collections中2分法的API
binarySearch
public static T int binarySearch(List? extends Comparable? super T list,
T key)使用二分搜索法搜索指定列表，以获得指定对象。在进行此调用之前，必须根据列表元素的自然顺序对列表进行升序排序（通过 sort(List) 方法）。如果没有对列表进行排序，则结果是不确定的。如果列表包含多个等于指定对象的元素，则无法保证找到的是哪一个。
此方法对“随机访问”列表运行 log(n) 次（它提供接近固定时间的位置访问）。如果指定列表没有实现 RandomAccess 接口并且是一个大型列表，则此方法将执行基于迭代器的二分搜索，执行 O(n) 次链接遍历和 O(log n) 次元素比较。
参数：
list - 要搜索的列表。
key - 要搜索的键。
返回：
如果搜索键包含在列表中，则返回搜索键的索引；否则返回 (-(插入点) - 1)。插入点 被定义为将键插入列表的那一点：即第一个大于此键的元素索引；如果列表中的所有元素都小于指定的键，则为 list.size()。注意，这保证了当且仅当此键被找到时，返回的值将 = 0。
抛出：
ClassCastException - 如果列表中包含不可相互比较 的元素（例如，字符串和整数），或者搜索键无法与列表的元素进行相互比较。
--------------------------------------------------------------------------------
binarySearch
public static T int binarySearch(List? extends T list,
T key,
Comparator? super T c)使用二分搜索法搜索指定列表，以获得指定对象。在进行此调用之前，必须根据指定的比较器对列表进行升序排序（通过 sort(List, Comparator) 方法）。如果没有对列表进行排序，则结果是不确定的。如果列表包含多个等于指定对象的元素，则无法保证找到的是哪一个。
此方法对“随机访问”的列表运行 log(n) 次（它提供接近固定时间的位置访问）。如果指定列表没有实现 RandomAccess 接口并且是一个大型列表，则此方法将执行基于迭代器的二分搜索，执行 O(n) 次链接遍历和 O(log n) 次元素比较。
参数：
list - 要搜索的列表。
key - 要搜索的键。
c - 排序列表的比较器。null 值指示应该使用元素的自然顺序。
返回：
如果搜索键包含在列表中，则返回搜索键的索引；否则返回 (-(插入点) - 1)。插入点 被定义为将键插入列表的那一点：即第一个大于此键的元素索引；如果列表中的所有元素都小于指定的键，则为 list.size()。注意，这保证了当且仅当此键被找到时，返回的值将 = 0。
抛出：
ClassCastException - 如果列表中包含使用指定的比较器不可相互比较 的元素，或者使用此比较器无法相互比较搜索键与列表元素。
java．util．Comparator接口。
A int compare(T o1,T o2)比较用来排序的两个参数。根据第一个参数小于、等于或大于第二个参数分别返回负整数、零或正整数。
在前面的描述中，符号 sgn(expression) 表示 signum 数学函数，根据 expression 的值为负数、0 还是正数，该函数分别返回 -1、0 或 1。
实现程序必须确保对于所有的 x 和 y 而言，都存在 sgn(compare(x, y)) == -sgn(compare(y, x))。（这意味着当且仅当 compare(y, x) 抛出异常时 compare(x, y) 才必须抛出异常。）
实现程序还必须确保关系是可传递的：((compare(x, y)0) (compare(y, z)0)) 意味着 compare(x, z)0。
最后，实现程序必须确保 compare(x, y)==0 意味着对于所有的 z 而言，都存在 sgn(compare(x, z))==sgn(compare(y, z))。
虽然这种情况很普遍，但并不 严格要求 (compare(x, y)==0) == (x.equals(y))。一般说来，任何违背这个条件的 Comparator 都应该清楚地指出这一事实。推荐的语言是“注意：此 Comparator 强行进行与 equals 不一致的排序。”
参数：
o1 - 要比较的第一个对象。
o2 - 要比较的第二个对象。
返回：
根据第一个参数小于、等于或大于第二个参数分别返回负整数、零或正整数。
抛出：
ClassCastException - 如果参数的类型不允许此 Comparator 对它们进行比较。
B boolean equals(Object obj)指示某个其他对象是否“等于”此 Comparator。此方法必须遵守 Object.equals(Object) 的常规协定。此外，仅当 指定的对象也是一个 Comparator，并且强行实施与此 Comparator 相同的排序时，此方法才返回 true。因此，comp1.equals(comp2) 意味着对于每个对象引用 o1 和 o2 而言，都存在 sgn(comp1.compare(o1, o2))==sgn(comp2.compare(o1, o2))。
注意，不 重写 Object.equals(Object) 方法总是 安全的。然而，在某些情况下，重写此方法可以允许程序确定两个不同的 Comparator 是否强行实施了相同的排序，从而提高性能。
覆盖：
类 Object 中的 equals
参数：
obj - 要进行比较的引用对象。
返回：
仅当指定的对象也是一个 Comparator，并且强行实施与此 Comparator 相同的排序时才返回 true。
以及java.lang.Comparable
public interface ComparableT此接口强行对实现它的每个类的对象进行整体排序。这种排序被称为类的自然排序，类的 compareTo 方法被称为它的自然比较方法。
实现此接口的对象列表（和数组）可以通过 Collections.sort（和 Arrays.sort）进行自动排序。实现此接口的对象可以用作有序映射中的键或有序集合中的元素，无需指定比较器。
对于类 C 的每一个 e1 和 e2 来说，当且仅当 e1.compareTo(e2) == 0 与 e1.equals(e2) 具有相同的 boolean 值时，类 C 的自然排序才叫做与 equals 一致。注意，null 不是任何类的实例，即使 e.equals(null) 返回 false，e.compareTo(null) 也将抛出 NullPointerException。
建议（虽然不是必需的）最好使自然排序与 equals 一致。这是因为在使用自然排序与 equals 不一致的元素（或键）时，没有显式比较器的有序集合（和有序映射表）行为表现“怪异”。尤其是，这样的有序集合（或有序映射表）违背了根据 equals 方法定义的集合（或映射表）的常规协定。
例如，如果将两个键 a 和 b 添加到没有使用显式比较器的有序集合中，使 (!a.equals(b) a.compareTo(b) == 0)，那么第二个 add 操作将返回 false（有序集合的大小没有增加），因为从有序集合的角度来看，a 和 b 是相等的。
实际上，所有实现 Comparable 的 Java 核心类都具有与 equals 一致的自然排序。java.math.BigDecimal 是个例外，它的自然排序将值相等但精确度不同的 BigDecimal 对象（比如 4.0 和 4.00）视为相等。
从数学上讲，定义给定类 C 上自然排序的关系式 如下：
{(x, y)|x.compareTo(y) = 0}。
整体排序的商 是：
{(x, y)|x.compareTo(y) == 0}。
它直接遵循 compareTo 的协定，商是 C 的等价关系，自然排序是 C 的整体排序。当说到类的自然排序与 equals 一致 时，是指自然排序的商是由类的 equals(Object) 方法定义的等价关系。
{(x, y)|x.equals(y)}。
compareTo
int compareTo(T o)比较此对象与指定对象的顺序。如果该对象小于、等于或大于指定对象，则分别返回负整数、零或正整数。
实现类必须确保对于所有的 x 和 y 都存在 sgn(x.compareTo(y)) == -sgn(y.compareTo(x)) 的关系。（这意味着如果 y.compareTo(x) 抛出一个异常，则 x.compareTo(y) 也要抛出一个异常。）
实现类还必须确保关系是可传递的：(x.compareTo(y)0 y.compareTo(z)0) 意味着 x.compareTo(z)0。
最后，实现者必须确保 x.compareTo(y)==0 意味着对于所有的 z，都存在 sgn(x.compareTo(z)) == sgn(y.compareTo(z))。 强烈推荐 (x.compareTo(y)==0) == (x.equals(y)) 这种做法，但并不是 严格要求这样做。一般来说，任何实现 Comparable 接口和违背此条件的类都应该清楚地指出这一事实。推荐如此阐述：“注意：此类具有与 equals 不一致的自然排序。”
在前面的描述中，符号 sgn(expression) 指定 signum 数学函数，该函数根据 expression 的值是负数、零还是正数，分别返回 -1、0 或 1 中的一个值。
参数：
o - 要比较的对象。
返回：
负整数、零或正整数，根据此对象是小于、等于还是大于指定对象。
抛出：
ClassCastException - 如果指定对象的类型不允许它与此对象进行比较。
