秩序配列の二分ルックアップ実装

1.整列配列、決定値の検索

実現する

#include
#include

using namespace std;


int binarySearch(vector& array, int target) {
    int left = 0, right = array.size();
    while (left < right) {
        int mid = (left + right) / 2;
        if (array[mid] == target) return mid;
        else if (array[mid] < target) left = mid + 1;
        else right = mid;
    }
    return -1;
}


int main(int argc, char const *argv[]) {
    vector input{1,2,3,4,5,6};
    cout << binarySearch(input, 3) << endl;
    cout << binarySearch(input, 100) << endl;
    cout << binarySearch(input, -100) << endl;

    return 0;
}

しゅつりょく
2 -1 -1 
まとめ

right初期化:right=arra.size()

サイクル条件:left

right値の更新:right=mid

 

実現二

#include
#include

using namespace std;

int binarySearch(vector& array, int target) {
    int left = 0, right = array.size() - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (array[mid] == target) return mid;
        else if (array[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

int main(int argc, char const *argv[]) {
    vector input{1,2,3,4,5,6};
    cout << binarySearch(input, 3) << endl;
    cout << binarySearch(input, 100) << endl;
    cout << binarySearch(input, -100) << endl;
    return 0;
}

しゅつりょく
2 -1 -1 
まとめ

right初期化:right=arra.size() - 1

サイクル条件:left<=right

right値の更新:right=mid-1

2.整列配列、不確定値の検索

2.1最初の目標値以上の数を検索

#include #include
using namespace std;
int binarySearch(vector& array, int target) {     int left = 0, right = array.size();     while (left < right) {         int mid = left + (right - left)/2;         if (array[mid] < target) left = mid + 1;         else right = mid;     }     return right; }
int main(int argc, char const *argv[]) {     vector input{2, 4, 5, 6, 9};     cout << binarySearch(input, 3) << endl;     cout << binarySearch(input, 100) << endl;     cout << binarySearch(input, -100) << endl;     return 0; }
しゅつりょく
1 5//ターゲット値が配列内のすべての要素より大きい場合、最後の要素インデックス0しか出力できません.
に質問
ターゲット値が配列内のすべての要素より大きい場合、最後の要素インデックスのみが出力されます.
まとめ

right初期化:right=arra.size()

サイクル条件:left

right値の更新:right=mid

サイズ判定:array[mid]

等しいか否かを判断する必要はない:array[mid]==target

2.2最後の目標値より小さい数を検索する

「≪ターゲット値以上の最初の数を検索｜Find First Number of Target Value｜emdw≫」から、次の操作を行います.
return right;
ターゲット値より小さい最後の数を検索します.
return right - 1;
#include #include
using namespace std;
int binarySearch(vector& array, int target) {     int left = 0, right = array.size();     while (left < right) {         int mid = left + (right - left)/2;         if (array[mid] < target) left = mid + 1;         else right = mid;     }     return right - 1; }
int main(int argc, char const *argv[]) {     vector input{2, 4, 5, 6, 9};     cout << binarySearch(input, 3) << endl;     cout << binarySearch(input, 100) << endl;     cout << binarySearch(input, -100) << endl;     return 0; }
しゅつりょく
0 4-1//ターゲット値が配列内のすべての要素より小さい場合、-1のみ出力できます.
に質問
ターゲット値が配列内のすべての要素より小さい場合は、-1のみ出力できます.
まとめ

right初期化:right=arra.size()

サイクル条件:left

right値の更新:right=mid

サイズ判定:array[mid]

等しいか否かを判断する必要はない:array[mid]==target

2.3目標値より大きい最初の数を検索する

ターゲット値以下の最初の数を検索

if (nums[mid] < target) left = mid + 1;

ターゲット値より大きい最初の数を検索

if (nums[mid] <= target) left = mid + 1;

#include #include
using namespace std;
int binarySearch(vector& array, int target) {     int left = 0, right = array.size();     while (left < right) {         int mid = left + (right - left)/2;         if (array[mid] <= target) left = mid + 1;         else right = mid;     }     return right; }
int main(int argc, char const *argv[]) {     vector input{2, 4, 5, 6, 9};     cout << binarySearch(input, 3) << endl;     cout << binarySearch(input, 100) << endl;     cout << binarySearch(input, -100) << endl;     return 0; }
しゅつりょく
1 5//ターゲット値が配列内のすべての要素より大きい場合、結果は最後の要素インデックス0を出力します.
に質問
ターゲット値が配列内のすべての要素より大きい場合、結果は最後の要素インデックスを出力します.

2.4目標値より大きい最初の数を検索する

ターゲット値より大きい最初の数を検索

return right;

ターゲット値以下の最後の数を検索

return right - 1;

#include #include
using namespace std;
int binarySearch(vector& array, int target) {     int left = 0, right = array.size();     while (left < right) {         int mid = left + (right - left)/2;         if (array[mid] <= target) left = mid + 1;         else right = mid;     }     return right - 1; }
int main(int argc, char const *argv[]) {     vector input{2, 4, 5, 6, 9};     cout << binarySearch(input, 3) << endl;     cout << binarySearch(input, 100) << endl;     cout << binarySearch(input, -100) << endl;     return 0; }
しゅつりょく
0 4-1//ターゲット値がすべての要素より小さい場合は、-1のみを返します.
に質問
ターゲット値が配列内のすべての要素より大きい場合、結果は最後の要素インデックスを出力します.

3秩序配列の回転

3.1ケース一：固定target値なし

3.1.1実現一

ソースコード
#include #include
using namespace std;
int binarySearch(vector& array) {     int left = 0, right = (int)array.size() - 1;     while (left < right) {         int mid = left + (right - left)/2;         if (array[mid] > array[right]) left = mid + 1;         else right = mid;     }     return nums[right]; }
int main(int argc, char const *argv[]) {     vector input{4,5,6,7,0, 1,2};     cout << "no repeat element:"<< binarySearch(input) << endl;
    vector input2{6,6,6,6,6,6,0,1,1,1,6,6};     cout << "has repeat element:"<< binarySearch(input2) << endl;     return 0; }
しゅつりょく
no repeat element:0 has repeat element:6
に質問

配列に重複値が含む場合を処理できない

.

のテスト例には、{6,6,0,1,1,1,6,6}がバグ

をテストできないなどの要件があります.

3.1.2実現二

#include #include
using namespace std;
int binarySearch(vector& array) {     int left = 0, right = (int)array.size() - 1;     while (left < right) {         int mid = (left + right)/2;         if (array[mid] > array[right]) {             left = mid + 1;         } else if (array[mid] < array[right]) {             right = mid;         } else {             --right;         }     }     return nums[right]; }
int main(int argc, char const *argv[]) {     vector input{4,5,6,7,0, 1,2};     cout << "no repeat element:"<< binarySearch(input) << endl;
    vector input2{6,6,6,6,6,6,0,1,1,1,6,6};     cout << "has repeat element:"<< binarySearch(input2) << endl;     return 0; }
しゅつりょく
no repeat element:0 has repeat element:0 
この場合、配列に重複要素が含まれている場合でも最小値を見つけることができます
3.1.3総括

right初期化:array.size() - 1

サイクル条件:left

配列に重複要素がある場合、array[mid]=array[right]:--right

を処理する必要があります.

3.2ケース2：固定target値あり

実現する

#include #include
using namespace std;
int binarySearch(vector& array, int target) {     int left = 0, right = (int)array.size() - 1;     while (left <= right) {         int mid = (left + right)/2;         if (array[mid] == target) return mid;         if (array[mid] < array[right]) {             if (array[mid] < target && target <= array[right]) {                 left = mid + 1;             } else {                 right = mid - 1;             }         } else {             if (target < array[mid] && target >= array[left]) {                 right = mid - 1;             } else {                 left = mid + 1;             }         }     }     return -1; }
int main(int argc, char const *argv[]) {     vector input{4,5,6,7,0,1,2};     cout << "no repeat element:"<< binarySearch(input, 0) << endl;     vector input2{3,1,1};     cout << "has repeat element:"<< binarySearch(input2, 3) << endl;     return 0; }
しゅつりょく
no repeat element:4 has repeat element:-1 
に質問
重複する要素がある場合、問題が発生する可能性があります.

実現二

#include #include
using namespace std;
int binarySearch(vector& array, int target) {     int left = 0, right = (int)array.size() - 1;     while (left <= right) {         int mid = (left + right)/2;         if (array[mid] == target) return mid;         if (array[mid] < array[right]) {             if (array[mid] < target && target <= array[right]) {                 left = mid + 1;             } else {                 right = mid - 1;             }         } else if (array[mid] > array[right]){             if (target < array[mid] && target >= array[left]) {                 right = mid - 1;             } else {                 left = mid + 1;             }         } else {             --right;         }     }     return -1; }
int main(int argc, char const *argv[]) {     vector input{4,5,6,7,0,1,2};     cout << "no repeat element:"<< binarySearch(input, 0) << endl;
    vector input2{3,1,1};     cout << "has repeat element:"<< binarySearch(input2, 3) << endl;     return 0; }
しゅつりょく
no repeat element:4 has repeat element:0 
まとめ

right初期化:array.size() - 1

サイクル条件:left

配列に重複要素がある場合、array[mid]=array[right]:--right

を処理する必要があります.