折半查找java

Ⅰ 白盒测试：用折半查找法在元素呈升序排列的数组中查找值为 key 的元素

动漫班上华鑫的作业吧……
/坏笑

Ⅱ 如何用java代码实现在一个已排列好的数组中找出小于等于给定x的位数下标（用二分查找做）

importjava.util.Arrays;

importjava.util.Random;

publicclassTest{

publicint[]getRandom(intlen){

int[]nums=newint[len<=0?10:len];

Randomrandom=newRandom();

for(inti=0;i<nums.length;i++){

nums[i]=random.nextInt(100);

}

returnnums;

}

publicIntegergetIndex(int[]nums,intvalue,intstartIndex,intendIndex){

if(startIndex==endIndex){

returnstartIndex;

}

intindex=(startIndex+endIndex)/2;

if(nums[index]==value){

returnindex;

}elseif(startIndex+1==endIndex&&nums[endIndex]>value){

returnendIndex;

}elseif(nums[index]>value){

returngetIndex(nums,value,startIndex,index);

}else{

returngetIndex(nums,value,index,endIndex);

}

}

publicstaticvoidmain(String[]args){

Testtest=newTest();

intvalue=50;

intlen=10;

int[]nums=test.getRandom(len);

Arrays.sort(nums);

Integerindex=test.getIndex(nums,value,0,nums.length-1);

System.out.println(Arrays.toString(nums));

System.out.println(value);

System.out.println(index);

}

}

Ⅲ 用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

二分查找也称折半查找（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;
}}
运行结果演示：

总结：

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

Ⅳ java程序，用折半查找法判断一个从键盘输入的数是否包含在该指定区间的数组元素中。

是不是这样的。。。。作业棚或明天交，十分捉急
编写一个链握伍java 应用程序，首先对一个数组指定区间内包含的元素进行排序，然后使用折半查找法判断一个从键盘输入的数是否包含在该指定区间的数组元素中。

参考使用的方法：

java.util.Arrays类中实现数组指定区间包含的元素排序的方法是：

void sort(double[] a, int fromIndex,int
toIndex)

java.util.Arrays类中实现在数组指定区间包含的元素中采用折皮差半查找算法查找指定数据的方法是：

int binarySearch(double[] a,
int
fromIndex, int
toIndex,
double
key)

Ⅵ JAVA面试题：3道问答题！

1：堆栈都是内存的可用区域，但是 堆的速度慢容量大，栈的速度快容量小。一个64K的字符串，自然放在堆。栈的内存是很宝贵的。
2：接口和抽象类都是面向对象编程的特点，都是可继承（实现）为明确的类。一般：所描述的事物（事件）属于很抽象的，则先使用接口表达这个事物，然后使用抽象类实现划分出各种分类事物。例如：List 接口下有抽象类：AbstractSequentialList<E> AbstractList<E>等，然后才有LinkedList ArrayList
3：如果这两个重复的数字没有说出其大小。并且数组是有序的，那就挨着比较2个相邻的数。或者：
int i=0;
Set<Integer> set=new HashSet<Integer>();
for(;i<array.length;i++)
if(set.add(array[i])) break;

array[i];//就是了

Ⅶ java实现折半查找 循环结束的条件看不懂

二分法查找（折半查找）的时间复杂度是O(log2n)

即是最坏的情况比较次数是2为底2n的对数。也就数如果数组长度为2，最坏的情况比较2两次谨扰；数组长度为16，最坏的情况比较5次；数组长度1204，最坏的情况是比较11次 就可以找到这个值或者确定找不到这个值。

你的代码就是通大缺过判断比较的次数来决定是否结束循环，当已比较（循环）次数大于最坏情况的次数还没有结束（number != a[middle]），则说明数组中不存在这个值。不过这里是用的N/2来近似的判断。

另一种更普遍的写法

publicclassDemo{
publicstaticvoidmain(String[]args){

//你原来的代码

System.out.println(Arrays.toString(a));
Scannerscanner=newScanner(System.in);
System.out.println("输入整数，程序判断该整数是否在数组中:");
intnumber=scanner.nextInt();

intindex=binary(a,number);
if(index==-1){
滚晌辩System.out.printf("%d不在数组中.
",number);
}else{
System.out.printf("%d在数组中,在数组中的位置下标是%d.",number,index);
}
}

privatestaticintbinary(int[]array,intvalue){
intstart=0;
intend=array.length-1;
while(start<=end){
intmiddle=(start+end)/2;
if(value==array[middle]){
returnmiddle;
}elseif(value>array[middle]){
start=middle+1;
}else{
end=middle-1;
}
}
return-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]||data>dataset[endIndex]||beginIndex>endIndex){
return -1;
}
if(data <dataset[midIndex]){
return binarySearch(dataset,data,beginIndex,midIndex-1);
}else if(data>dataset[midIndex]){
return binarySearch(dataset,data,midIndex+1,endIndex);
}else {
return midIndex;
}
}

}

Ⅸ 46. 对110个元素的有序表用折半查找法进行查找时，求最大、最小比较次数

反复递归即可 最漏陆小当然是一碧氏次啦 最大就是不停的找
代码如下
import java.util.Scanner;
public class HalfSearch {
static StringBuffer bf = new StringBuffer();
static int a = 0;
static int count = 0;
public static void main(String args[]) {
Scanner scanner = new Scanner(System.in);
System.out.println("请输入要查找的数");
a = scanner.nextInt();
Search(0,110);
System.out.println(bf +" "+ count);
}
public static int Search(int min , int max) {
int half = (max+min)/2;
if (a <悔搜散 half) {
bf.append(half).append(";");
count++;
return Search(min,half);
}
else if (a > half){
bf.append(half).append(";");
count++;
return Search(half, max);
}
else {
bf.append(half);
count++;
return a;
}
}
}