java的二分查找算法

❶ 什么叫java中的二分查找法

1、算法概念。

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

2、算法思想。

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

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

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

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

3、实现思路。

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

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

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

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

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

4、实现代码。

/**
*description:二分查找。
*@paramarray需要查找的有序数组
*@paramfrom起始下标
*@paramto终止下标
*@paramkey需要查找的关键字
*@return
*/
publicstatic<EextendsComparable<E>>intbinarySearch(E[]array,intfrom,intto,Ekey)throwsException{
if(from<0||to<0){
("paramsfrom&lengthmustlargerthan0.");
}
if(from<=to){
intmiddle=(from>>>1)+(to>>>1);//右移即除2
Etemp=array[middle];
if(temp.compareTo(key)>0){
to=middle-1;
}elseif(temp.compareTo(key)<0){
from=middle+1;
}else{
returnmiddle;
}
}
returnbinarySearch(array,from,to,key);
}

❷ 常见查找和排序算法

查找成功最多要n 次，平均（n+1）/2次， 时间复杂度为O(n) 。
优点：既适用顺序表也适用单链表，同时对表中元素顺序无要求，给插入带来方便，只需插入表尾即可。
缺点：速度较慢。

改进：在表尾设置一个岗哨，这样不用去循环判断数组下标是否越界，因为最后必然成立。

适用条件：

二分查找的判定树不仅是二叉排序树，而且是一棵理想平衡树。 时间复杂度为O(lbn) 。

循环实现

递归实现

待排序的元素需要实现 Java 的 Comparable 接口，该接口有 compareTo() 方法，可以用它来判断两个元素的大小关系。

从数组中选择最小元素，将它与数组的第一个元素交换位置。再从数组剩下的元素中选择出最小的元素，将它与数组的第二个元素交换位置。不断进行这样的操作，直到将整个数组排序。

选择排序需要 ~N2/2 次比较和 ~N 次交换，==它的运行时间与输入无关==，这个特点使得它对一个已经排序的数组也需要这么多的比较和交换操作。

从左到右不断 交换相邻逆序的元素 ，在一轮的循环之后，可以让未排序的最大元素上浮到右侧。

在一轮循环中，如果没有发生交换，那么说明数组已经是有序的，此时可以直接退出。

每次都 将当前元素插入到左侧已经排序的数组中 ，使得插入之后左侧数组依然有序。

对于数组 {3, 5, 2, 4, 1}，它具有以下逆序：(3, 2), (3, 1), (5, 2), (5, 4), (5, 1), (2, 1), (4, 1)，插入排序每次只能交换相邻元素，令逆序数量减少 1，因此插入排序需要交换的次数为逆序数量。

==插入排序的时间复杂度取决于数组的初始顺序，如果数组已经部分有序了，那么逆序较少，需要的交换次数也就较少，时间复杂度较低==。

对于大规模的数组，插入排序很慢，因为它只能交换相邻的元素，每次只能将逆序数量减少 1。希尔排序的出现就是为了解决插入排序的这种局限性，它通过交换不相邻的元素，每次可以将逆序数量减少大于 1。

希尔排序使用插入排序对间隔 h 的序列进行排序。通过不断减小 h，最后令 h=1，就可以使得整个数组是有序的。

希尔排序的运行时间达不到平方级别，使用递增序列 1, 4, 13, 40, ... 的希尔排序所需要的比较次数不会超过 N 的若干倍乘于递增序列的长度。后面介绍的高级排序算法只会比希尔排序快两倍左右。

归并排序的思想是将数组分成两部分，分别进行排序，然后归并起来。

归并方法将数组中两个已经排序的部分归并成一个。

将一个大数组分成两个小数组去求解。

因为每次都将问题对半分成两个子问题，这种对半分的算法复杂度一般为 O(NlogN)。

先归并那些微型数组，然后成对归并得到的微型数组。

取 a[l] 作为切分元素，然后从数组的左端向右扫描直到找到第一个大于等于它的元素，再从数组的右端向左扫描找到第一个小于它的元素，交换这两个元素。不断进行这个过程，就可以保证左指针 i 的左侧元素都不大于切分元素，右指针 j 的右侧元素都不小于切分元素。当两个指针相遇时，将切分元素 a[l] 和 a[j] 交换位置。

快速排序是原地排序，不需要辅助数组，但是递归调用需要辅助栈。

快速排序最好的情况下是每次都正好将数组对半分，这样递归调用次数才是最少的。这种情况下比较次数为 CN=2CN/2+N，复杂度为 O(NlogN)。

最坏的情况下，第一次从最小的元素切分，第二次从第二小的元素切分，如此这般。因此最坏的情况下需要比较 N2/2。为了防止数组最开始就是有序的，在进行快速排序时需要随机打乱数组。

因为快速排序在小数组中也会递归调用自己，对于小数组，插入排序比快速排序的性能更好，因此在小数组中可以切换到插入排序。

最好的情况下是每次都能取数组的中位数作为切分元素，但是计算中位数的代价很高。一种折中方法是取 3 个元素，并将大小居中的元素作为切分元素。

对于有大量重复元素的数组，可以将数组切分为三部分，分别对应小于、等于和大于切分元素。

三向切分快速排序对于有大量重复元素的随机数组可以在线性时间内完成排序。

快速排序的 partition() 方法，会返回一个整数 j 使得 a[l..j-1] 小于等于 a[j]，且 a[j+1..h] 大于等于 a[j]，此时 a[j] 就是数组的第 j 大元素。

可以利用这个特性找出数组的第 k 大的元素。

该算法是线性级别的，假设每次能将数组二分，那么比较的总次数为 (N+N/2+N/4+..)，直到找到第 k 个元素，这个和显然小于 2N。

堆中某个节点的值总是大于等于其子节点的值，并且堆是一颗完全二叉树。

堆可以用数组来表示，这是因为堆是完全二叉树，而完全二叉树很容易就存储在数组中。位置 k 的节点的父节点位置为 k/2，而它的两个子节点的位置分别为 2k 和 2k+1。这里不使用数组索引为 0 的位置，是为了更清晰地描述节点的位置关系。

在堆中，当一个节点比父节点大，那么需要交换这个两个节点。交换后还可能比它新的父节点大，因此需要不断地进行比较和交换操作，把这种操作称为上浮。

类似地，当一个节点比子节点来得小，也需要不断地向下进行比较和交换操作，把这种操作称为下沉。一个节点如果有两个子节点，应当与两个子节点中最大那个节点进行交换。

将新元素放到数组末尾，然后上浮到合适的位置。

从数组顶端删除最大的元素，并将数组的最后一个元素放到顶端，并让这个元素下沉到合适的位置。

把最大元素和当前堆中数组的最后一个元素交换位置，并且不删除它，那么就可以得到一个从尾到头的递减序列，从正向来看就是一个递增序列，这就是堆排序。

一个堆的高度为logN，因此在堆中插入元素和删除最大元素的复杂度都为 logN。

对于堆排序，由于要对 N 个节点进行下沉操作，因此复杂度为 NlogN。

堆排序是一种原地排序，没有利用额外的空间。

现代操作系统很少使用堆排序，因为它无法利用局部性原理进行缓存，也就是数组元素很少和相邻的元素进行比较和交换。

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，==计数排序要求输入的数据必须是有确定范围的整数==。

当输入的元素是 n 个 0 到 k 之间的整数时，它的==运行时间是 O(n + k)==。计数排序不是比较排序，排序的速度快于任何比较排序算法。由于用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。比较适合用来排序==小范围非负整数数组的数组==。

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：

同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。

当输入数据均匀分配到每一个桶时最快，当都分配到同一个桶时最慢。

实间复杂度N*K

快速排序是最快的通用排序算法，它的内循环的指令很少，而且它还能利用缓存，因为它总是顺序地访问数据。它的运行时间近似为 ~cNlogN，这里的 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;
}}
运行结果演示：

总结：

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

❹ 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问题

什么是二分查找？

二分查找也称折半查找（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镄刡inarySearch锛堬级鏂规硶

姒傝堪

binarysearch涓哄湪鎸囧畾鏁扮粍涓镆ユ垒鎸囧畾鍊煎缑绱㈠紩鍊硷纴璇ュ煎湪锣冨洿鍐呮垒寰楀埌鍒栾繑锲炶ュ肩殑绱㈠紩鍊硷纴镓句笉鍒板垯杩斿洖璇ュ肩殑鎻掑叆浣岖疆锛屽傛灉璇ュ煎ぇ浜庢寚瀹氲寖锲存渶澶у煎垯杩斿洖-锛坢axlength+1锛夛纴钥岋细

int w=Arrays.binarySearch(a,1,5,8); 镆ユ垒镄勮寖锲翠负绱㈠紩鍊1-5,锛2,3,4,5,6

8骞朵笉鍦ㄦよ寖锲翠腑锛屼笖8澶т簬链澶х储寮曞肩殑6锛屾墍浠ヨ繑锲-锛5+1锛夛细-6

瑙ｆ瀽

镆ョ湅java婧愮爜锛屽彲浠ョ湅鍒帮纴binarySearch锛堬级鏂规硶鏄閲嶈浇鏂规硶锛屾彁渚涗简涓ょ嶅舰鍙傛柟寮忥细

灏忚创澹锛歜inarySearch锛堬级鏂瑰纺鍐呴儴瀹炵幇鐢ㄧ殑鏄浜屽垎娉曟煡镓撅纴镓浠ュ湪镆ユ垒鍓嶉渶瑕佸皢鏁扮粍杩涜屾帓搴忥纴涓旀暟缁勪腑涓嶈兘鍑虹幇鐩稿悓鍏幂礌锛屽惁鍒欐煡镓惧嚭𨱒ョ殑绱㈠紩浼氢笉娓呮氭槸鍝涓涓镄勶细

1锛夐粯璁よ寖锲达纸鏁扮粍闀垮害锛夋煡镓炬寚瀹氩肩储寮曪细

镙煎纺锛

binarySearch(object[ ], object key);

濡傛灉key鍦ㄦ暟缁勪腑锛屽垯杩斿洖鎼灭储鍊肩殑绱㈠紩锛涘惁鍒栾繑锲-1锛坘ey灏忎簬鏁扮粍涓镄勪换镒忎竴涓鍏幂礌锛夋垨钥呪-钬(鎻掑叆镣)銆傛彃鍏ョ偣鏄绱㈠紩阌灏呜佹彃鍏ユ暟缁勭殑闾ｄ竴镣癸纴鍗崇涓涓澶т簬璇ラ敭镄勫厓绱犵储寮曘

key镄勫煎湪鏁扮粍锣冨洿鍐呭垯绱㈠紩浠0寮濮嬭℃暟锛

key鍊间笉瀛桦湪鏁扮粍锣冨洿鍐咃纸澶т簬鏁扮粍链灏忓厓绱狅级鍒欎粠1寮濮嬭℃暟锛

瀹炰緥锛

importjava.util.Arrays;publicclasstest {publicstaticvoidmain(String[] args){int[]b=newint[]{4,25,10,95,06,21};System.out.println("铡熸暟缁勪负锛");for(intdim1:b){System.out.print(""+dim1+" ");}Arrays.sort(b);System.out.println("鎺掑簭钖庝负锛");for(intx:b){System.out.print(x+" ");}System.out.println();intindex=Arrays.binarySearch(b,2);System.out.println("鍏抽敭瀛2镄勮繑锲炲间负锛"+index);index=Arrays.binarySearch(b,20);System.out.println("鍏抽敭瀛20镄勮繑锲炲间负锛"+index);index=Arrays.binarySearch(b,30);System.out.println("鍏抽敭瀛30镄勮繑锲炲间负锛"+index);index=Arrays.binarySearch(b,100);System.out.println("鍏抽敭瀛100镄勮繑锲炲间负锛"+index);index=Arrays.binarySearch(b,10);System.out.println("鍏抽敭瀛10镄勮繑锲炲间负锛"+index);}}

//out:

鏁扮粍瀵逛簬姣忎竴闂ㄧ紪绋嬭瑷𨱒ヨ撮兘鏄閲嶈佺殑鏁版嵁缁撴瀯涔嬩竴锛屽綋铹朵笉钖岃瑷瀵规暟缁勭殑瀹炵幇鍙婂勭悊涔熶笉灏界浉钖屻

Java 璇瑷涓鎻愪緵镄勬暟缁勬槸鐢ㄦ潵瀛桦偍锲哄畾澶у皬镄勫悓绫诲瀷鍏幂礌銆

浣犲彲浠ュ０鏄庝竴涓鏁扮粍鍙橀噺锛屽 numbers[100] 𨱒ヤ唬镟跨洿鎺ュ０鏄 100 涓镫绔嫔彉閲 number0锛宯umber1锛....锛宯umber99銆

链鏁欑▼灏嗕负澶у朵粙缁 Java 鏁扮粍镄勫０鏄庛佸垱寤哄拰鍒濆嫔寲锛屽苟缁椤嚭鍏跺瑰簲镄勪唬镰併

Arrays 绫

java.util.Arrays 绫昏兘鏂逛究鍦版搷浣沧暟缁勶纴瀹冩彁渚涚殑镓链夋柟娉曢兘鏄闱欐佺殑銆

鍏锋湁浠ヤ笅锷熻兘锛

• 缁欐暟缁勮祴鍊硷细阃氲繃 fill 鏂规硶銆

• 瀵规暟缁勬帓搴忥细阃氲繃 sort 鏂规硶,鎸夊崌搴忋

• 姣旇缉鏁扮粍锛氶氲繃 equals 鏂规硶姣旇缉鏁扮粍涓鍏幂礌鍊兼槸钖︾浉绛夈

• 镆ユ垒鏁扮粍鍏幂礌锛氶氲繃 binarySearch 鏂规硶鑳藉规帓搴忓ソ镄勬暟缁勮繘琛屼簩鍒嗘煡镓炬硶镎崭綔銆

1 public static int binarySearch(Object[] a, Object key)

鐢ㄤ簩鍒嗘煡镓剧畻娉曞湪缁椤畾鏁扮粍涓鎼灭储缁椤畾鍊肩殑瀵硅薄(Byte,Int,double绛)銆傛暟缁勫湪璋幂敤鍓嶅繀椤绘帓搴忓ソ镄勚傚傛灉镆ユ垒鍊煎寘钖鍦ㄦ暟缁勪腑锛屽垯杩斿洖鎼灭储阌镄勭储寮曪绂钖﹀垯杩斿洖 (-(鎻掑叆镣) - 1)銆

2 public static boolean equals(long[] a, long[] a2)

濡傛灉涓や釜鎸囧畾镄 long 鍨嬫暟缁勫郊姝ょ浉绛夛纴鍒栾繑锲 true銆傚傛灉涓や釜鏁扮粍鍖呭惈鐩稿悓鏁伴噺镄勫厓绱狅纴骞朵笖涓や釜鏁扮粍涓镄勬墍链夌浉搴斿厓绱犲归兘鏄鐩哥瓑镄勶纴鍒栾や负杩欎袱涓鏁扮粍鏄鐩哥瓑镄勚傛崲鍙ヨ瘽璇达纴濡傛灉涓や釜鏁扮粍浠ョ浉钖岄‘搴忓寘钖鐩稿悓镄勫厓绱狅纴鍒欎袱涓鏁扮粍鏄鐩哥瓑镄勚傚悓镙风殑鏂规硶阃傜敤浜庢墍链夌殑鍏朵粬锘烘湰鏁版嵁绫诲瀷锛圔yte锛宻hort锛孖nt绛夛级銆

3 public static void fill(int[] a, int val)

灏嗘寚瀹氱殑 int 鍊煎垎閰岖粰鎸囧畾 int 鍨嬫暟缁勬寚瀹氲寖锲翠腑镄勬疮涓鍏幂礌銆傚悓镙风殑鏂规硶阃傜敤浜庢墍链夌殑鍏朵粬锘烘湰鏁版嵁绫诲瀷锛圔yte锛宻hort锛孖nt绛夛级銆

4 public static void sort(Object[] a)

瀵规寚瀹氩硅薄鏁扮粍镙规嵁鍏跺厓绱犵殑镊铹堕‘搴忚繘琛屽崌搴忔帓鍒椼傚悓镙风殑鏂规硶阃傜敤浜庢墍链夌殑鍏朵粬锘烘湰鏁版嵁绫诲瀷锛圔yte锛宻hort锛孖nt绛夛级銆

❼ 用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;
}

}

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