二分探索
#include <bits/stdc++.h> using namespace std; #define NOT_FOUND -1 int binary_search(int A[],int n,int key) { int left = 0; int right =n; while(left<right){ int mid = (left+right)/2; if(A[mid]==key){ return mid; }else if(key<A[mid]){ right = mid; }else{ left = mid+1; } } return NOT_FOUND; } int main() { int A[11] = {1,2,2,3,5,7,10,11,11,12,41}; cout<<binary_search(A,11,2)<<endl;//2 cout<<binary_search(A,11,4)<<endl;//-1 cout<<binary_search(A,11,12)<<endl;//9 return 0; }
探索なので「ある」か「ないか」を返す.
探索している値が複数個ある場合は前から返すわけではないので注意.
binary_search(A,11,2)ではA[1],A[2]に2があり2を返している.