#include "search.h"


Search::Search()
{

}

int Search::SequenceSearch(vector<int> &arr, int key)
{
 for(int i=0;i< arr.size();i++){
 if(arr[i] == key)
 {
 cout<<"find key at:"<<i<<endl;
 return i;
 }

 }
 cout<<"failed find key "<<key<<endl;
 return -1;
}

int Search::binarySearch(const vector<int> &arr, int key)
{
 int low =0;
 int high =arr.size()-1;
 int mid ;
 while(low <= high){
 mid = low + (high -low)/2;
 if(arr[mid] == key)
 {
 cout<<"find key at:"<<mid<<endl;
 return mid;
 }
 if(arr[mid] < key){
 low = mid+1;
 }
 if(arr[mid] > key){
 high = mid-1;
 }
 }
 cout<<"failed find key "<<key<<endl;
 return -1;
}

int Search::binarySearch(const vector<int> &arr, int low, int high,int key)
{
 if(low < 0 || high > arr.size()){
 cout<<"rang is err"<<endl;
 return -1;
 }
 if(low > high){
 cout<<"failed find key "<<key<<endl;
 return -1;
 }
 int mid = low+ (high -low) /2;
 if(arr[mid] == key)
 {
 cout<<"find key at:"<<mid<<endl;
 return mid;
 }
 if(arr[mid] < key){
 return binarySearch(arr, mid+1, high,key);
 }
 if(arr[mid] > key){
 return binarySearch(arr, low, mid-1,key);
 }
}

//分布均匀下按比例查找
int Search::InsertionSearch(const vector<int> &arr, int low, int high, int key)
{
 if(low < 0 || high > arr.size()){
 cout<<"rang is err"<<endl;
 return -1;
 }
 if(low > high){
 cout<<"failed find key "<<key<<endl;
 return -1;
 }
 int mid = low+ (key - arr[low])/(arr[high] -arr[low]) * (high - low);
 if(arr[mid] == key)
 {
 cout<<"find key at:"<<mid<<endl;
 return mid;
 }
 if(arr[mid] < key){
 return binarySearch(arr, mid+1, high,key);
 }
 if(arr[mid] > key){
 return binarySearch(arr, low, mid-1,key);
 }
}

void Search::GetAllNotIncluded(vector<int> &A,vector<int> &B)
{
 vector<int> res;
 // 遍历B中每一个元素,每次用元素与 A中元素进行二分比较,不存在加入到结果中
 for (int i = 0; i < B.size(); i++) {
 int l = 0;
 int r = A.size() - 1;
 bool contains = false;
 while (l <= r) {
 int mid = l + ((r - l) >> 1);
 if (A[mid] == B[i]) {
 contains = true;
 break;
 }
 if (A[mid] > B[i]) {
 r = mid - 1;
 } else {
 l = mid + 1;
 }
 }
 if (!contains) {
 res.push_back(B[i]);
 }
 }

 cout <<endl<<"GetAllNotIncluded B "<<endl;
 for(auto i:res){
 cout <<i<<" ";
 }
 cout <<endl;
}