泛型化的折半查找法
1.题目
泛型是JAVA重要的特性，使用泛型编程，可以使代码复用率提高。
实现：查找作为泛型的一个简单应用，使用泛型实现折半查找法
2.解题思路
创建一个类：BinSearch。
折半查找要求数据集合中的元素必须可比较，并且各元素按升序或降序排列。取集合的中间元素作为比较对象，如:
(1)如果给定的值与比较对象相等，则查找成功，返回中间元素的序号。
(2)如果给定的值大于比较对象，则在中间元素的右半段进行查找。
(3)如果给定的值小于比较对象，则在中间元素的左半段进行查找。
3.代码详解
package com.xiaoxuzhu;
import java.util.Arrays;
/**
* Description:
*
* @author xiaoxuzhu
* @version 1.0
*
* <pre>
* 修改记录:
* 修改后版本 修改人 修改日期 修改内容
* 2022/5/10.1 xiaoxuzhu 2022/5/10 Create
* </pre>
* @date 2022/5/10
*/
public class BinSearch {
public static <T extends Comparable<? super T>> int search(T[] array, T key) {
int low = 0;
int mid = 0;
int high = array.length;
System.out.println("查找的中间值：");
while (low <= high) {
mid = (low high) / 2;
System.out.print(mid " ");
if (key.compareTo(array[mid]) > 0) {
low = mid 1;
} else if (key.compareTo(array[mid]) < 0) {
high = mid - 1;
} else {
System.out.println();
return mid;
}
}
return -1;
}
public static void main(String[] args) {
Integer[] ints = {1,2,3,4,5,6,7,8,9,10};
System.out.println("数据集合：");
System.out.println(Arrays.toString(ints));
System.out.println("元素3所对于的索引序号：" search(ints, 3));
}
}
知识点补充
折半查找法是效率较高的一种查找方法。假设有已经按照从小到大的顺序排列好的五个整数a0~a4，要查找的数是X，其基本思想是： 设查找数据的范围下限为l=0，上限为h=4，求中点m=（l h）/2，用X与中点元素am比较，若X等于am，即找到，停止查找；否则，若X大于am，替换下限l=m 1，到下半段继续查找；若X小于am，换上限h=m-1，到上半段继续查找；如此重复前面的过程直到找到或者l>h为止。如果l>h，说明没有此数，打印找不到信息，程序结束。
该方法是查找的范围不断缩小一半，所以查找效率较高。
下面将通过一个例题，带大家深入了解一下折半查找法
比如我买了一双鞋，你好奇问我多少钱，我说不超过300元。你还是好奇，你想知道到底多少，我就让你猜，你会 怎么猜？
答案：你每次猜中间数。
代码实现：
//只适合有序的数组
#include<stdlib.h>
#include<stdio.h>
int main()
{
int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int left = 0;
int right = sizeof(arr) / sizeof(arr[0]) - 1;
int key = 7;
int mid = 0;
while (left <= right)
{
mid = (left right) / 2;
if (arr[mid] > key)
{
right = mid - 1;
}
else if (arr[mid] < key)
{
left = mid 1;
}
else
{
break;
}
}
if (left <= right)
printf("找到了，下标是%d\n", mid);
else
printf("找不到");
system("pause");
return 0;
}
如何实现一个二分查找函数：
int bin_search(int arr[], int left, int right, int key)
{
int mid = 0;
while (left <= right)
{
int mid = (left right) >> 1;
if (arr[mid] > key)
right = mid - 1;
else if (arr[mid] < key)
left = mid 1;
else
return mid;
}
return -1;
}到此这篇关于Java利用泛型实现折半查找法的文章就介绍到这了,更多相关Java折半查找法内容请搜索Devmax以前的文章或继续浏览下面的相关文章希望大家以后多多支持Devmax！