Javaで二分探索を実装する方法

java でバイナリ検索を実装する方法

BinarySearch

名前としてのバイナリ検索これは、データを毎回 2 つの部分に分割し、その後必要なデータを見つけることを意味します。

このように考えることができます。二分探索は、私たちが通常行う価格推測ゲームに非常に似ています。価格を見積もる 審判は、価格が実際の価値と比較してどのくらい高いか安いかを伝え、低ければ確実に少し高い価格を提示します。逆も同様です。

(関連ビデオ チュートリアルの共有: java ビデオ チュートリアル)

バイナリ検索中、受信データは順序どおりである必要があります。現在は昇順であると仮定します。探している値を中央の値 (配列の左境界 (右境界 - 左境界)/2) と比較します。値が大きい場合は、中央の値の左側のデータを検索します。これより小さい場合は、中央の値の右側にあるデータが検索されます。

public class BinarySearch {
//进行二分法查找的前提是数组已经有序！
	public static int rank(int key,int nums[])
	{
		//查找范围的上下界
		int low=0;
		int high=nums.length-1;
		//未查找到的返回值
		int notFind=-1;
		while(low<=high)
		{
			//二分中点=数组左边界+(右边界-左边界)/2
			//整数类型默认取下整
			int mid=low+(high-low)/2;
			//中间值是如果大于key
			if(nums[mid]>key)
			{
				//证明key在[low,mid-1]这个区间
				//因为num[mid]已经判断过了所以下界要减一
				high=mid-1;
			}else if(nums[mid]<key)
			{
				//证明key在[mid+1,high]这个区间
				//同样判断过mid对应的值要从mid+1往后判断
				low=mid+1;
			}
			else
			{
				//查找成功
				return mid;
			}
		}
		//未成功
		return notFind;
	}
	public static void main(String[] args) {
		System.out.println("请输入数据数量：");
		Scanner scanner=new Scanner(System.in);
		int amount=scanner.nextInt();
		int num;
		int nums[]=new int[amount];
		int i=0;
		while(i<amount)
		{
			nums[i]=scanner.nextInt();
			i++;
		}
		Arrays.sort(nums);
		System.out.println("请输入想要查找的值");
		int key=scanner.nextInt();
		int answer=rank(key,nums);
		if(answer!=-1)
		{
			System.out.println("所查找的数据存在："+nums[answer]);
		}
		else
		{
			System.out.println("您所查找的数据不存在");
		}
	}
 
}

その他の Java チュートリアル については、PHP 中国語 Web サイトの Java チュートリアルの列に注目してください。

以上がJavaで二分探索を実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。