模拟java二分查找代码 二分查找代码实现java
JAVA二分查找
//*******二分查找,都注释了,复制所有代码,保存成QuickSortApp.java*************//
成都创新互联公司主要从事成都网站设计、网站制作、网页设计、企业做网站、公司建网站等业务。立足成都服务宁晋,10年网站建设经验,价格优惠、服务专业,欢迎来电咨询建站服务:13518219792
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的二分查找的程序代码
//你那程序太难改了,每个方法都单职责啊
public class Test6 {
//二分查找
public static int findPos(int[] a,int key) {
int start=0;
int end=a.length-1;
int temp=0;
while(startend){
int mid=(start+end)/2;
if(keya[mid]){
start=mid+1;
temp=start;
}else if(keya[mid]){
end=mid-1;
temp=end;
}else {
return mid;
}
}
return temp;
}
public static void main(String[] args) {
int[]array={1,4,6,7,10,11,23,78};
System.out.println(findPos(array, 0));
}
}
用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;
}
}
程序基本上就是这样了,其中注释中有详细的解释说明
分享文章:模拟java二分查找代码 二分查找代码实现java
本文URL:http://pwwzsj.com/article/ddojoij.html