【解決方法】ソートされた配列内の重複を含む二分探索

プログラミングQA

2023.05.19

[ad_1]

二分検索アルゴリズムを使用して、並べ替えられた配列の重複をすべてのインデックスとともに表示するにはどうすればよいですか。二分探索アルゴリズムは機能していますが、すべての重複を表示できません。誰かが助けて、これをどのように達成できるかを説明してもらえますか?
ありがとう。

私が試したこと:

検索アルゴリズム:

static int BinarySearch(int[] arr, int key)
        {
            int minNum = 0;
            int maxNum = arr.Length - 1;

            while (minNum <= maxNum)
            {
                int mid = (minNum + maxNum) / 2;
                if (key == arr[mid])
                {
                    return (++mid);
                }
                else if (key > arr[mid])
                {
                    minNum = mid + 1;
                }
                else
                {
                    maxNum = mid - 1;
                }
            }
            return -1;
        }

解決策 1
解決策 6

解決策 1

引用：

二分検索アルゴリズムを使用して、並べ替えられた配列の重複をすべてのインデックスとともに表示するにはどうすればよいですか。

簡単に言うと、そうではありません。それは目的ではありません。
二分探索では、必要な値の位置、または重複している場合は 1 つの値の位置のみが得られます。
すべての重複とインデックスを表示するには、二分検索ルーチンによって返された位置の周囲で二次検索を実行する必要があります。

C++

return (++mid);

ところで、なぜ一致する要素の位置に1を加えるのでしょうか？

解決策 6

次のようにしました：
整数配列[]= {1,2,5,5,5,6,8,9,10}; 、数値 = 5;
指定された `number` の最初の出現と最後の出現を検索します。

Java

helper_rec(arr, number, firstindex , lastindex){

	int mid = firstindex + lastindex/2;
	//base case
	if(arr[mid] == number){
		int tempmid=mid;
		while(arr[tempmid]==number && mid >=0){
			tempmid--;//2
		}
		if(arr[tempmid+1]==number{
			first = arr[tempmid+1];
		}
		tempmid =mid;//0
		while(arr[tempmid]==number && mid< arr.length){
			tempmid++;
		}
		if(arr[tempmid]==number){
			second =arr[tempmid-1];
		}
		return;
	}
	
	//recursive
	
	if(mid< number ){
		helper_rec(arr, number, mid+1, lastindex);
	}
	else{
		helper_rec(arr, number , 0 , mid);
	}
	return;
}