にぶんたんさく

二分探索は探索範囲を半分に分けて探索する方法である.
この探索の最大の利点は時間の複雑さがO(logn)であることである.
私たちはよく理解して使用する順序探索を理解し、最初から最後まで探索しています.
これはkey値があるかどうかを探す方法です.
シーケンシャルプローブ方式のWorstcaseでの時間的複雑度はO(n)である.
この探索の最も簡単な例は私たちが日常生活の中で遊んでいるUp&Downゲームです.
出題者が1~100で数字を決めて数字を当てるゲーム
このゲームをプレイするときは、まず1~100個の数字の中で一番真ん中の数字50を呼び出し、徐々に範囲を絞って推測します.この方式を用いることが二分探索である.

にぶんこうほうコード

public static int binarySearch(int[] arr,int key){
        int low = 0;
        int high = arr.length - 1;

        while(low <= high){

            int mid = (low + high) / 2;

            if(key < arr[mid]){
                high = mid - 1;
            }else if (key > arr[mid]){
                low = mid + 1;
            }else{
                return mid;
            }
        }
        return -1;
    }

次はこの探索のコードです.
まず,探索する配列arrと検索する数字を鍵で受信する.
次に、先頭と末尾を指定し、徐々に半分に減らし、配列内のキーのインデックス値を返します.
見つからない場合は、-1を返します.
しかし,このコードは配列内の繰返し値を考慮していない.

二分探索問題

白駿1920題

入力

は、N個のアレイでカウントされ、アレイでカウントされる(N個)
M個の検索する配列の数、配列中の数(M個)

アルゴリズム解析

package back_joon.Data_Structures;
import java.util.Arrays;
import java.util.Scanner;

public class b1920 {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int[] arr = new int[N];

        for(int i=0;i<N;i++){
            arr[i] = sc.nextInt();
        }

        // 이분탐색을 위한 정렬
        Arrays.sort(arr);

        int M = sc.nextInt();


        StringBuilder sb = new StringBuilder();
        for(int i=0;i<M;i++){
            if(binarySearch(arr,sc.nextInt()) >= 0){
                sb.append(1).append('\n');
            }else{
                sb.append(0).append('\n');
            }
        }
        System.out.println(sb);
    }

    /**
     * @param arr 정렬 된 배열
     * @param key 찾으려는 값
     * @return 찾으려는 값의 인덱스
     */
    public static int binarySearch(int[] arr,int key){
        int low = 0;
        int high = arr.length - 1;

        while(low <= high){

            int mid = (low + high) / 2;

            if(key < arr[mid]){
                high = mid - 1;
            }else if (key > arr[mid]){
                low = mid + 1;
            }else{
                return mid;
            }
        }
        return -1;
    }
}