(basic) Searching Linear, Binary(upper,lower bound)

 본 포스팅은 블로거가 개발언어의 개념정리 필요를 위한것입니다.

목차와 차례가 뒤죽박죽이며 오직 블로거의 편의목적을 위해 작성되었음을 알려드립니다. 

- Linear Searching

- Binary Searching

- Upper,Lower bound

 

 

 

 

- Linear Searching

 

https://www.geeksforgeeks.org/searching-algorithms/

 

~~
for(int i = 0 ; i < arr.length ; i++){
	if(arr[i] == find) return find
}
~~

 

 

- Binary Searching

 

https://www.geeksforgeeks.org/searching-algorithms/

Recursive

int bSearch(T arr[], T val, int first, int last)
{
    if (first > last) return -1;

    int mid = (first + last) / 2;
    if (val == arr[mid])
        return mid;
    else if (val < arr[mid])
        return bSearch(arr, val, first, mid – 1);
    else
        return bSearch(arr, val, mid + 1, last);
}

 

- Upper,Lower bound

 

n보다

Lowerbound : k >= n 이 되는 k의 인덱스

Upperbound : k >   n 이 되는 k의 인덱스

 

Lowerbound : 입력된 n이 행렬 arr[] 에서 구간 [s,e] 에서 arr[m(s+e/2)-1] < k , arr[m] >= k 가 되는 최소 m을 구하기

Upperbound : 입력된 n이 행렬 arr[] 에서 구간 [s,e] 에서 arr[m(s+e/2)-1] < k , arr[m] > k 가 되는 최소 m을 구하기

 

int upperbound(int arr[],int s,int e,int n){
	int m;
    while(s<e){
    	m = (s+e)/2;
        if(arr[m] <= n) s = m + 1;
        else e = m;
    }
	return e;
}

int lowerbound(int arr[],int s,int e,int n){
	int m;
    while(s<e){
    	m = (s+e)/2;
        if(arr[m] < n) s = m + 1;
        else e = m;
    }
	return e;
}

부등호 차이만 있다.