アルゴリズム系列(二)検索アルゴリズム--基本検索と二分検索

アルゴリズムシリーズ(一)基本概念の一文では,アルゴリズム基本概念,アルゴリズム複雑度評価,常用アルゴリズム証明方式を簡単に紹介した.この文章では、検索アルゴリズムを紹介します.主に二分検索アルゴリズムです.
n個の元素のうちA 0,A 1...から.An−1では,見つけるべき要素xを見つけ,最も簡単な方法はn個の要素を遍歴し,要素xを見つけるとxの位置を返すアルゴリズムであり,このアルゴリズムの時間的複雑度はO(n)である.
このn個の要素が秩序化されている場合、最初から最後まで巡回する必要がなく、検索する要素を見つけることができ、二分法を使用することができます.二分検索の時間的複雑さはO(lgn)である.
二分検索の前提は元素秩序(一般的には昇順)であり、基本思想は中間元素A[m]と検索する元素xを比較することであり、等しい場合はすでに発見され、A[m]がxより大きい場合は、探している元素は必ずA[m]の前にあり、A[m]がxより小さい場合は、探している元素は必ずA[m]の後ろにある.検索は一度も行われず,配列規模は半減した.検索する要素が見つかるか、現在のサブ配列が空になるまで、サブ配列の規模を半減します.
たとえば、[1,2,3,4,5]で2を検索します.
最初に見つかった数字の下付き文字は(0+4)/2=2で、見つかった数字は3,3<2で、探している数字の位置は[0,2]の間にあります.
2回目に見つかった数字の下付きは(0+1)/2=0で、見つかった数字は1,1<2で、探している数字は(0,1)の間にあります.
3回目に見つかった数字の下付き文字は(1+1)/2=1で、数字2が見つかり、見つかった位置を返す.
このときに見つかった数字が1でない場合は、配列に探している数字がないことを示します.
注意すべき点は区間位置であり、A[m]がxに等しくない以上、次はmという位置から探すのではなく、m+1を次の開始位置、またはm-1を次の開始位置とする
二分検索には2つの実装方式があり、1つは再帰実装であり、1つは非再帰実装である.
ダイレクトコード

package com.algorithm.tree;

import java.util.Arrays;

/**
 *     
 * 
 * @author chao
 *
 */
public class BinarySearchTree {
	/**
	 *        
	 * 
	 * @param num
	 * @param number
	 * @return
	 */
	public static int binarySearch(int num[], int number) {
		if (num == null || num.length == 0) {
			return -1;
		}
		int start, end, mid;
		start = 0;
		end = num.length - 1;
		while (start <= end) {
			mid = (start + end) / 2;
			if (num[mid] == number)
				return mid;
			else if (num[mid] > number) {
				end = mid - 1;
			} else {
				start = mid + 1;
			}
		}
		return -1;
	}

	/**
	 *     
	 * 
	 * @param num
	 * @param number
	 * @return
	 */
	public static int RecursivebinarySearch(int num[], int start, int end, int key) {
		int mid = (start + end) / 2;
		if (num == null || num.length == 0 || key < num[start] || key > num[end]) {
			return -1;
		} else if (num[mid] > key) {
			return RecursivebinarySearch(num, start, mid - 1, key);
		} else if (num[mid] < key) {
			return RecursivebinarySearch(num, mid + 1, end, key);
		} else {
			return mid;
		}

	}

	public static void main(String[] args) {
		int num[] = { 3, 5, 7, 9, 10 };
		Arrays.sort(num);
		System.out.println(binarySearch(num, 7));
		System.out.println(binarySearch(num, 8));
		System.out.println(RecursivebinarySearch(num, 0, num.length - 1, 7));
		System.out.println(RecursivebinarySearch(num, 0, num.length - 1, 8));
	}
}

ここでのソートはjavaのapiをそのまま使用しており、後でソートアルゴリズムについて詳しく説明します
アルゴリズム実装コードgithubアドレスはhttps://github.com/robertjc/simplealgorithm
あとはどんどん補充していきますので、問題があるかもしれませんが、よろしくお願いします.
QRコードをスキャンして、私の公衆アカウントに注目してください.