So implementieren Sie die binäre Suche in Java

So implementieren Sie die binäre Suche in Java

BinarySearch

Binäre Suche, wie der Name schon sagt schlägt vor, die Daten jedes Mal in zwei Teile aufzuteilen und dann die gewünschten Daten zu finden.

Wir können uns die binäre Suche so vorstellen, dass sie dem Preisschätzspiel, das wir normalerweise spielen, sehr ähnlich ist Geben Sie einen Preis an. Der Schiedsrichter wird Ihnen sagen, wie hoch oder niedrig der Preis im Verhältnis zum wahren Wert ist. Wenn er niedriger ist, werden wir Ihnen auf jeden Fall einen etwas höheren Preis nennen und umgekehrt.

(Weitergabe verwandter Video-Tutorials: Java-Video-Tutorial)

Während der binären Suche müssen die eingehenden Daten ab und zu in aufsteigender Reihenfolge sortiert werden Vergleichen Sie jeweils den gesuchten Wert mit dem mittleren Wert (Array linker Rand + (rechter Rand - linker Rand)/2). Wenn er größer ist, wird nach den Daten auf der linken Seite des mittleren Werts gesucht kleiner ist, wird nach den Daten auf der rechten Seite des Mittelwerts gesucht.

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("您所查找的数据不存在");
		}
	}
 
}

Weitere Java-Tutorials finden Sie in der Spalte „Java-Tutorials“ auf der chinesischen PHP-Website.

Das obige ist der detaillierte Inhalt vonSo implementieren Sie die binäre Suche in Java. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!