定番面接問題のまとめ——Binary Searchとその変種

int findMin(int a[], int lower, int upper)
{
	if(a[lower] <= a[upper]) //  2 case， 1：        2:           ，          
	{
		return lower;
	}
	int m = (lower + upper)/2;

	if(a[m] >= a[lower] )//   lower ... m      ，              ，          m + 1, upper. 
	{                    //               6 1     ，       m == lower
		return findMin(a, m+1, upper);
	}
	else
	{
		return findMin(a, lower, m); //        
	}
}
int main() // generate test case
{
	int a[10];
	for( int i = 0; i < 6; i++)
	{
		for( int j = 0; j < 6; j++)
		{
			a[ (i + j)%6] = j;
		}
		for( int j = 0; j < 6; j++)
		{
			printf("%d ", a[j]);
		}
		printf("
Min at %d
", findMin(a, 0, 5));
	}
	return 0;
}

int findLowerBound(int a[], int nSize, int query)
{
	int lower, upper;
	int m;
	lower = 0, upper = nSize - 1;

	while(lower <= upper)
	{
		m = (lower + upper)>>1;

		if(a[m] == query)
		{
			while(a[--m] == query);
			return m+1;
		}
		else if(a[m] > query)
		{
			upper = m - 1;
		}
		else
		{
			lower = m + 1;
		}
	}

	return -1;
}

int findUpperBound(int a[], int nSize, int query)
{
	int lower, upper, m;

	lower = 0, upper = nSize - 1;

	while(lower <= upper)
	{
		m = (lower + upper) >> 1;

		if(a[m] == query)
		{
			while(a[++m] == query);
			return m-1;
			
		}
		else if(a[m] > query)
		{
			upper = m - 1;

		}
		else
		{
			lower = m + 1;
		}
	}
	return -1;
}
int main() //generate test case
{
	int a[] = {1, 2, 2, 3, 3, 3, 5, 5, 5}; //size is 9
	int l, u;
	//int *p =  lower_bound(a, a + 9, 0);
 	for( int i = 0; i < 7; i++)
 	{
 		l = findLowerBound(a, 9, i);
 		u = findUpperBound(a, 9, i);
		if( l != -1)
		{
			printf("l:%d u:%d  (u-l):%d
", l, u, u - l + 1); 
		}
		else
		{
			printf("Can't find
");
		}
 	}
	return 0;

}

#include <stdio.h>

int bsearch_lowerbound(int a[],int n,int x)
{
	int l=0,r=n-1;
	while(l+1<r){
		int m=(l+r)/2;
		if(a[m]>=x)
			r=m;
		else
			l=m+1;
	}
	if(a[l]==x)
		return l;
	else if(a[r]==x)
		return r;
	else
		return -1;
}

int bsearch_upperbound(int a[],int n,int x)
{
	int l=0,r=n-1;
	while(l+1<r){
		int m=(l+r)/2;
		if(a[m]<=x)
			l=m;
		else
			r=m-1;
	}
	if(a[r]==x)
		return r;
	else if(a[l]==x)
		return l;
	else
		return -1;
}

int main()
{
	int a[] = {1,1, 2, 3, 3,3, 5};

	

	
	for(int i = 0; i < 6; i++)
	{
		printf("%d
", bsearch_lowerbound(a, 7, i));
	}

	return 0;
}

//1 4 5 8 ---> 7
int FindFirstLarger(int a[], int nSize, int query)
{
	int lower = 0; 
	int upper = nSize - 1;
	int m ;
	while(lower <= upper)
	{
		m = (lower + upper) / 2;
		
		if(a[m] < query)
		{
			lower = m + 1;
		}
		else
		{
			upper = m - 1;
		}
	}
	return lower;
}
int main()
{
	int a[] = {1, 4, 5, 8}; //size is 9
	
	for(int i = 0; i < 10; i++)
	{
		printf("i: %d  at: %d
", i, FindFirstLarger(a, 4, i));
	}

	return 0;
}

bool SearchInRowColSortedMatrix(const int data[], int nRow, int nCol, int query, int &tRow, int &tCol)
{
     int iRow, iCol;
     
     iRow = 0;
     iCol = nCol - 1;
     int t; 
     while(iRow < nRow && iCol >= 0)
     {
         t = data[iRow * nCol + iCol];//get the current data. 
         
         if( t == query) //find it
         {
             tRow = iRow;
             tCol = iCol;
             return true;
         }
         else if( t < query) // eleminate the rest of the elements in the current row, who are less than t. 
         {
             iRow++;
         }
         else //eleminate all the rest elements in current col, who are greater than t.
         {
             iCol--;
         }
     }
     return false;
}