java二分排序

A. 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;j<nElems;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(rightPtr>0 && theArray[--rightPtr]>pivot);//空循环，从rightPrt往leftPrt方向开始找一个比pivot小的数，用rightPrt记录元素的位置,并且rightPtr>0会保证不会数组越界。
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;j<maxSize;j++){
long n = (int)(java.lang.Math.random()*99);//产生随机数。
arr.insert(n); //用insert方法为arr中的成员数组变量赋值。
}
arr.display(); //用display方法显示arr中成员变量数组中的所有元素。
arr.quickSort(); //用quickSort方法为arr成员变量数组中的元素按从小到大排序。
arr.display(); //显示。
}
}

B. 用Java语言编写对整型数组进行二分查找的程序。

public class BinarySearchDemo {

public static void main(String[] args) {
int[] a = new int[]{1,5,7,9,11,18,23,48,69};
int point = new BinarySearchDemo().binarySearch(a, 23);

if(point == -1)
System.out.println("在数组中未查找到数23");
else
System.out.println("数字23是数组中第 " + (point + 1) + " 位数");

}

/**
* 二分法查找一个整数在整型数组中的位置
*
* 算法思路：首先得到数组a的最小值和最大值的下标，分别是：low和high，接着求出值位于数组中间那个数的下标middle
* 然后再将这个middle对应的数组中的数和待查找的数num进行比较，如果相等，则表示已查找到，如果num < a[middle]
* 则说明num位于a[low]和a[middle]之间，于是将a[middle - 1]设为较大值，继续求出此时对应的a[middle]，
* 再进行比较，其他情况可依次类推。一直到low=high，如果此时还没有在数组a中查找到，则说明该数组a中没有值num，返回-1
*
* @param a 给定的整型数组
* @param num 待查找的数 num
*
* @return 返回整数num在数组a中的位置下标，如果未查找到则返回-1
* */
public int binarySearch(int[] a,int num){
int low = 0;
int high = a.length - 1;

while(low <= high){
int middle = (low + high) / 2;
if(num == a[middle])
return middle;
else if(num < a[middle])
high = middle - 1;
else
low = middle + 1;
}

return -1;
}

}

程序基本上就是这样了，其中注释中有详细的解释说明

C. 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;
}}
运行结果演示：

总结：

递归相较于循环，代码比较简洁，但是时间和空间消耗比较大，效率低。在实际的学习与工作中，根据情况选择使用。通常我们如果使用循环实现代码只要不是太繁琐都选择循环的方式实现~

D. jave二分算法

import java.util.ArrayList;
import java.util.Random;

public class Test {
public static void main(String[] args) {
ArrayList<Integer> list=new ArrayList<Integer>(50);//创建一个容量50的ArrayList
Random r=new Random(47);
for(int i=0;i<50;i++){
list.add(r.nextInt(200));//添加50个200以内的随机数
}
BinSort(list);//二分插入排序
System.out.println(list);//谨祥唯输出list的内容
}
public static void BinSort(ArrayList<Integer> list){//考虑到有大宴首量的随机访祥培问，用ArrayList较快
int left, right, mid, temp;
for (int i = 1; i < list.size(); i++)
{
left = 0;
right = i - 1;
temp = list.get(i);
while (left <= right)
{
mid = (left + right)/2;
if (temp < list.get(mid)) //升序
right = mid - 1;
else
left = mid + 1;
}
for (int j = i - 1; j >= left; j--)
list.set(j + 1, list.get(j));
list.set(left, temp);
}
}
}

E. 关于java的binarysearch()方法

Java中的binarySearch方法是一种用于在有序数组中查找特定元素的算法。其方法主要基于二分查找法实现，能快速地在有序数组中定位指定元素的位置。下面是具体的方法和解释：

Java中的binarySearch方法是基于二分查找法的实现，用于在有序数组中查找特定元素。此方法返回的是指定元素在数组中的索引值，若不存在则返回负值。同时，使用该方法需要注意数组必须是有序的。

具体解释：

基本介绍与工作原理

Java的binarySearch方法是数组工具类java.util.Arrays中的一个方法。该方法基于二分查找算法实现，适用于已排序的数组。二分查找算法的核心思想是不断缩小搜索范围，每次将搜索范围缩小一半，直到找到目标元素或搜索范围为空。这种方法的时间复杂度为O，相对于线性查找的O，在处理大规模数据时效率更高。

方法参数与返回值

binarySearch方法接受三个参数：待搜索的数组、待搜索元素的起始位置和结束位置。它会返回目标元素在数组中的位置索引，如果数组中没有该元素，则返回负值。插入点的定义是如果插入元素会导致数组保持有序的最小索引位置。所以如果没有找到目标元素，该方法将指示我们如何将元素添加到数组中保持其有序性。

使用注意事项

使用binarySearch方法时，必须确保数组是有序的。如果数组未排序，结果将不可预测。此外，对于大型数组，该方法非常高效；但对于小型数组，可能不如简单的线性搜索来得直观和快速。在实际应用中，应根据具体情况选择使用哪种搜索方法。同时，由于该方法涉及复杂的算法逻辑，开发者在使用时需要有相应的编程基础和算法知识。

总结来说，Java中的binarySearch方法是一种高效的搜索算法，适用于在已排序的数组中查找特定元素。它的核心思想是二分查找法，能够在逐步缩小搜索范围的同时快速定位目标元素的位置。

F. java中对一个list用shuffle后，再用collection.binarySearch法找其中的元素，为啥下标会出现负值啊

在Java中使用shuffle方法对一个列表进行洗牌后，列表中的元素将变得无序。此时，如果你尝试使用Collections的binarySearch方法进行二分查找，由于列表已不再有序，二分查找算法将无法正常工作。

二分查找算法要求在查找前列表是有序的，它通过比较目标值与中间元素来决定搜索方向，从而将搜索范围缩小一半。若列表是无序的，二分查找将无法根据中间元素进行有效判断，导致结果不可靠。因此，即使返回了某个下标，也不能保证该下标对应的元素就是你所寻找的目标。

当binarySearch方法在无序列表中查找元素时，它会返回一个负值，这个负值实际上是负的插入点。具体来说，返回值是-(插入点+1)，而插入点是指在查找过程中，如果在列表中插入目标元素，它应该插入的位置。这表明目标元素并不在列表中，或者插入点的位置意味着目标元素应该位于列表中的某个位置。

例如，如果你在一个无序的列表中查找某个元素，binarySearch方法可能返回-4，这意味着如果要将该元素插入到列表中，它应该插入在列表的第4个位置之前。实际上，这个返回值表示的是目标元素不在列表中，或者列表中的元素不满足二分查找的有序条件。

所以，当使用shuffle方法对列表进行洗牌后，再用binarySearch方法查找元素时，出现负值下标是正常的，这表明列表已不再有序，二分查找无法正确执行，结果自然不可信。为了获得正确的查找结果，你需要先对列表进行排序。