#include <bits/stdc++.h>
using namespace std;

int main() {
	vector<int> arr={11,12,13,14,15,16,17,18};
	int k=15;
	// for(int i=0;i<arr.size();i++){ //linear search
	// 	if(arr[i]==15){
	// 		cout<<"wow"<<endl;
	// 	}else{
	// 		cout<<"."<<endl;
	// 	}
	// }
	
	//for binary search array is always sorted..  O(log2N)
	int start=0,end=arr.size()-1;
	int mid=(start+end)/2;
	while(start<=end){
		if(arr[mid]==k){
			cout<<"found: "<<mid<<endl;
			break;
		}else if(arr[mid]>k){
			end=mid-1;
			
			cout<<"bada"<<endl;
			
		}else{
			start=mid+1;
			cout<<"chota"<<endl;
		}
		mid=(start+end)/2;
	
	}
	return 0;
}