投稿日 9/1/2019最終更新日 9/1/2019

# 目次

目次
- アルゴリズム
- コード

配列の最後の要素に探索対象を上書きし「番兵」をおき、必ず対象が見つかるようにする.
これによりループ内から探索対象との比較の条件分岐を１つ減らすことができる.

# アルゴリズム

配列の末尾が対象と等しければ真を返して終了
配列の末尾の要素を後で復元するために一時退避
配列の末尾を対象で上書きする
探索インデックスを０で初期化
探索インデックスにおける配列の要素が対象と異なる間次に進める
配列の末尾の要素を一時退避から復元する
探索が番兵で終了した場合は偽、それより前で終了した場合は真を返す

# コード

C++

// C++ 14
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <math.h>

#define ll long long
#define Int int
#define loop(x, start, end) for(Int x = start; x < end; x++)
#define loopdown(x, start, end) for(int x = start; x > end; x--)
#define rep(n) for(int x = 0; x < n; x++)
#define span(a,x,y) a.begin()+x,a.begin()+y
#define span_all(a) a.begin(),a.end()
#define len(x) (x.size())
#define last(x) (*(x.end()-1))

using namespace std;


bool search(vector<int> v, int target) {
    if (v[v.size() - 1] == target) return true; // 1
    int stash = v[v.size() - 1]; // 2
    v[v.size() - 1] = target; // 3
    int i = 0; // 4
    while (v[i] != target) i++; // 5
    v[v.size() - 1] = stash; // 6
    return i != v.size() - 1; // 7
}