Skip to content

Instantly share code, notes, and snippets.

@abhishek2x
Created December 19, 2020 13:59
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save abhishek2x/8f8f5b9bf10d4751aa18240ae334b713 to your computer and use it in GitHub Desktop.
Save abhishek2x/8f8f5b9bf10d4751aa18240ae334b713 to your computer and use it in GitHub Desktop.
Finding a position on an Element in an infinite array
/*!
* Copyright (c) 2020 Abhishek Srivastava
*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
int binaryPlay(vector<int> a, int l, int h, int key){
while(l<=h){
int mid = l + (h-l)/2;
if(a[mid] == key){
return mid;
} else if(a[mid] < key){
l = mid+1;
} else {
h = mid-1;
}
}
return -1;
}
int main(){
ios :: sync_with_stdio(false);
cin.tie(0);
vector<int> inf = {1, 2, 3, 4, 5, 6, 7 ,8 , 9, 10};
int key = 4;
int l = 0, h = 1, mid;
while(inf[h] < key){
h = h*2;
}
// cout << h << "\t";
cout << binaryPlay(inf, l, h, key);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment