#include <bits/stdc++.h>
using namespace std;
int BinarySearch(vector<int> arr, int key)
{
	int start =0, end = arr.size()-1;
	while(start<=end)
	{
		int mid = start + (end-start)/2;
 
		if(arr[mid]==key)
		{
			return mid;
		}
		else if(key<arr[mid])
		{
			end  = mid-1;
		}
		else
		{
			start = mid+1;
		}
	}
	return -1;
}
int main() {
	// your code goes here
	vector<int> arr = {1,3,4,6,7,8};
 
	cout<<BinarySearch(arr,8)<<endl;
 
	return 0;
}

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CmludCBCaW5hcnlTZWFyY2godmVjdG9yPGludD4gYXJyLCBpbnQga2V5KQp7CglpbnQgc3RhcnQgPTAsIGVuZCA9IGFyci5zaXplKCktMTsKCXdoaWxlKHN0YXJ0PD1lbmQpCgl7CgkJaW50IG1pZCA9IHN0YXJ0ICsgKGVuZC1zdGFydCkvMjsKCQkKCQlpZihhcnJbbWlkXT09a2V5KQoJCXsKCQkJcmV0dXJuIG1pZDsKCQl9CgkJZWxzZSBpZihrZXk8YXJyW21pZF0pCgkJewoJCQllbmQgID0gbWlkLTE7CgkJfQoJCWVsc2UKCQl7CgkJCXN0YXJ0ID0gbWlkKzE7CgkJfQoJfQoJcmV0dXJuIC0xOwp9CmludCBtYWluKCkgewoJLy8geW91ciBjb2RlIGdvZXMgaGVyZQoJdmVjdG9yPGludD4gYXJyID0gezEsMyw0LDYsNyw4fTsKCQoJY291dDw8QmluYXJ5U2VhcmNoKGFyciw4KTw8ZW5kbDsKCQoJcmV0dXJuIDA7Cn0=