C++での二分探索

6107 ワード
Binary Search テキストリンク

1.スケジュールの数値配列が指定されている場合、昇順ソートで数値が何番目にあるかを指定するコード(ゼロから)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int main() {
	freopen("input.txt", "rt", stdin);
	int n;
	vector<int> V;
	int want_to_find;
	int lt, mid, rt;
	
	cin >> n;
	for(int i=0; i<n; i++) {
		int temp;
		cin >> temp;
		V.push_back(temp);
	}
	
	cin >> want_to_find;
	sort(V.begin(), V.end());
	lt = 0;
	rt = n-1;
	while(lt <= rt) {
		mid = (lt+rt) / 2;
		if(V[mid] == want_to_find) {
			cout << mid;
			return 0;
		}
		else if(V[mid] > want_to_find) rt = mid - 1;
		else if(V[mid] < want_to_find) lt = mid + 1;
	}

	return 0;
}
  • V[mid]=want to find:検索する要素が見つかった場合.
  • V[mid]>want to find:検索する要素がもっと小さい場合、rt=mid-1;
  • V[mid]ex)
    5
    13 5 11 7 23
    23
    • CSS Wrap-Up
    派遣グループ