プログラマが理解すべき検索(java実装)

先週はランキングについていくつかのブログを書いて、たくさんの道友の支持を得て、ここでとても感謝しています.
ソートを比較すると、今日の検索は簡単ですが、今日はまず次のようにします.
1、シーケンシャル検索
2、半角検索
 
一、順序検索の基本思想:
テーブルの端から順番にテーブルをスキャンし、スキャンしたノードキーと所定の値(aと仮定)を順番に比較し、現在のノードキーがaと等しい場合は検索に成功し、スキャンが終了してもキーワードがaと等しいノードが見つからない場合は検索に失敗する.
 
はっきり言って、最初から最後まで、一つ一つ比べて、同じものを探して成功して、見つからないと失敗します.明らかな欠点は、検索効率が低いことです.
 
リニア・テーブルのシーケンス・ストレージ構造とチェーン・ストレージ構造に適しています.
検索平均の長さを計算します.
例えば上の表では、1を検索するには1回、2を検索するには2回、順に下に押すと、16を検索するには16回、
これらの検索回数を合計するだけで(中学校では、底に高さを乗じて2で割る)、次いで結点数で割ると平均検索長であることがわかります.
n=ノード数を設定
平均ルックアップ長=(n+1)/2
 
Javaで実現:

import java.util.Scanner;

public class SequentialSearch {
	int a[]={49,38,65,97,76,13,27,49,78,34,12,64,5,4,62,99,98,54,56,17,18,23,34,15,35,25,53,51};
	public SequentialSearch(){
		System.out.println("         ：");
		Scanner input=new Scanner(System.in);
		int input1=input.nextInt();
		for(int i=0;i

 
二、二分法検索(折半検索)の基本思想:
 
前提:
(1)この区間の中点位置を決定する:mid=(low+high)/2
minは区間の中間の接点の位置を表し、lowは区間の最も左の接点の位置を表し、highは区間の最も右の接点の位置を表す
(2)検索対象のa値をノードmidのキーワード(以下R[mid].key)と比較し、等しい場合は検索に成功し、そうでない場合は新しい検索区間を決定する.
R[mid].key>aは、表の秩序性から分かる、R[mid].keyの右側の値はいずれもaより大きいので、aに等しいキーワードが存在する場合、必ずR[mid]になる.keyの左の表にあります.このときhigh=mid-1
R[mid].key
R[mid].key=aの場合、検索に成功します.
(3)次のルックアップ新しいルックアップ区間について、手順(1)と(2)を繰り返す
(4)検索中にlowが徐々に増加し,highが徐々に減少し,low>highであれば検索に失敗する.
 
 
平均ルックアップ長=Log 2(n+1)-1
 
注意:二分法は効率的ですが、テーブルをキーワードでソートします.ソート自体は時間のかかる演算であるため,二分法は順序記憶構造に適している.テーブルの秩序性を維持するには、シーケンス構造で多くのノードを挿入および削除する必要があります.したがって、二分ルックアップは、確立されると変更が少なく、常にルックアップが必要な線形テーブルに特に適している.
だから、折半で検索するときはシーケンスが秩序正しくなければなりません.
 
Javaで実現:

import java.util.ArrayList;
import java.util.List;

public class binarySearch {
public binarySearch(){
	List list=new ArrayList();
	for(int i=0;i<10000;i+=2){             // list      1-10000     ，      ，   ，     ！
		list.add(i);                       //         
	}
	int low=0;
	int high=list.size();
	int key=3334;
	while(low<=high){
		int mid=(low+high)/2;
		if(key==list.get(mid)){
			System.out.println("    list     ："+mid);
			break;
		}
	if(key>list.get(mid)){
		low=mid+1;          //    ， low      ，high    
	}
	if(keyhigh){
	System.out.println("      ！");
	}
}
}

 
  

  
 
  
 
 
  
           ，    java   ，      ，         ：
 
  
http://blog.csdn.net/shan9liang/article/details/7555811
 
  
               《    》，              。