Java利用泛型實(shí)現(xiàn)折半查找法

更新時(shí)間：2022年08月19日 11:34:00 作者：小虛竹and掘金

泛型是JAVA重要的特性，使用泛型編程，可以使代碼復(fù)用率提高。查找作為泛型的一個(gè)簡(jiǎn)單應(yīng)用，本文將使用泛型實(shí)現(xiàn)折半查找法，感興趣的可以了解一下

泛型化的折半查找法

1.題目

泛型是JAVA重要的特性，使用泛型編程，可以使代碼復(fù)用率提高。

實(shí)現(xiàn)：查找作為泛型的一個(gè)簡(jiǎn)單應(yīng)用，使用泛型實(shí)現(xiàn)折半查找法

2.解題思路

創(chuàng)建一個(gè)類：BinSearch。

折半查找要求數(shù)據(jù)集合中的元素必須可比較，并且各元素按升序或降序排列。取集合的中間元素作為比較對(duì)象，如:

(1)如果給定的值與比較對(duì)象相等，則查找成功，返回中間元素的序號(hào)。

(2)如果給定的值大于比較對(duì)象，則在中間元素的右半段進(jìn)行查找。

(3)如果給定的值小于比較對(duì)象，則在中間元素的左半段進(jìn)行查找。

3.代碼詳解

package com.xiaoxuzhu;
import java.util.Arrays;
/**
 * Description:
 *
 * @author xiaoxuzhu
 * @version 1.0
 *
 * <pre>
 * 修改記錄:
 * 修改后版本	        修改人		修改日期			修改內(nèi)容
 * 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("數(shù)據(jù)集合：");
        System.out.println(Arrays.toString(ints));
        System.out.println("元素3所對(duì)于的索引序號(hào)："+search(ints, 3));
    }
}

知識(shí)點(diǎn)補(bǔ)充

折半查找法是效率較高的一種查找方法。假設(shè)有已經(jīng)按照從小到大的順序排列好的五個(gè)整數(shù)a0~a4，要查找的數(shù)是X，其基本思想是：設(shè)查找數(shù)據(jù)的范圍下限為l=0，上限為h=4，求中點(diǎn)m=（l+h）/2，用X與中點(diǎn)元素am比較，若X等于am，即找到，停止查找；否則，若X大于am，替換下限l=m+1，到下半段繼續(xù)查找；若X小于am，換上限h=m-1，到上半段繼續(xù)查找；如此重復(fù)前面的過(guò)程直到找到或者l>h為止。如果l>h，說(shuō)明沒(méi)有此數(shù)，打印找不到信息，程序結(jié)束。

該方法是查找的范圍不斷縮小一半，所以查找效率較高。

下面將通過(guò)一個(gè)例題，帶大家深入了解一下折半查找法

比如我買了一雙鞋，你好奇問(wèn)我多少錢，我說(shuō)不超過(guò)300元。你還是好奇，你想知道到底多少，我就讓你猜，你會(huì) 怎么猜？

答案：你每次猜中間數(shù)。

代碼實(shí)現(xiàn)：

//只適合有序的數(shù)組
#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("找到了，下標(biāo)是%d\n", mid);
    else
        printf("找不到");
    system("pause");
    return 0;
}

如何實(shí)現(xiàn)一個(gè)二分查找函數(shù)：

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

到此這篇關(guān)于Java利用泛型實(shí)現(xiàn)折半查找法的文章就介紹到這了,更多相關(guān)Java折半查找法內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: