Binary Search

Binary Search

01. বাইনারি সার্চ – ১(শাফায়েত আশরাফ)
02. বাইনারি সার্চ - ২(বাইসেকশন) - শাফায়েত আশরাফ
03. বাইসেকশন মেথড - আহমাদ ফাইয়াজ
04. বাইনারি সার্চ - হাসান আবদুল্লাহ
05. Painless Binary Search - আবু আসিফ খান চৌধুরী
06. Binary Search part - 1 - শাকিল আহমেদ
07. TopCoder Tutorial
08. One Problem from Spoj
09. Chinese problem solving blog
10. Good Resource (***)
11. HackerEarth1, HackerEarth2
12. TopCoder
13. GeeksForGeeks

Randomized Binary Search Algorithm

Visualization

	#include<bits/stdc++.h>
	using namespace std;
	/*
	Problem Statement: You are given an array v[1 ... N].
	There is some x for which, v[i] = 0 for all i in the range 1 <= i <= k, and a[i] = 1 for all i in the range k + 1 <= i <= N. We want to find this position k which splits the groups of 0s and 1s.
	*/
	void FindX(vector<int>& v)
	{
	int lo = 1, hi = v.size() - 1, mid;
	while(lo < hi){
	mid = (lo + hi+1)/2;
	if(v[mid] == 0) lo = mid;
	else hi = mid - 1;
	}
	if(v[lo] == 0)cout << lo << endl;
	else cout << "Array is all 1s\n";
	}
	int main()
	{
	int n;
	cin >> n;
	vector<int> v(n+1);
	for(int i = 1; i <= n; i++){
	cin >> v[i];
	}
	FindX(v);
	}

view raw binarySearch.cpp hosted with ❤ by GitHub

Share: