/*
////이분탐색
int arr[500], n;
int bs(int s, int e, int k)
{
int mid=(s+e)/2;
if(s>e) return -1;
if(arr[mid]==k) return mid;
else if(arr[mid]>k) bs(s,mid-1,k);
else bs(mid+1,e,k);
}
int main()
{
int i,k;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&arr[i]);
}
scanf("%d",&k);
printf("%d",bs(1,n,k));
}
*/
/*
3002
#include <stdio.h>
int a[1000001];
int b[100001];
int n, m;
int bs(int s, int e, int k) {
int mid=(s+e)/2;
if(s>e) return -1;
if(a[mid]==k) return mid;
else if(a[mid]>k) bs(s,mid-1,k);
else bs(mid+1,e,k);
}
int main() {
int i, j, k;
scanf("%d", &n);
for(i=1; i<=n; i++) {
scanf("%d", &a[i]);
}
scanf("%d", &m);
for(j=1; j<=m; j++) {
scanf("%d", &k);
printf("%d ", bs(1, n, k));
}
}
*/
/*
2633
#include <stdio.h>
int a[100001];
int n;
int bs(int s, int e, int k)
{
int mid=(s+e)/2;
if(s==e)
{
if(a[s]>=k)
return s;
else
return n+1;
}
if(a[mid]>=k)
bs(s, mid, k);
else
bs(mid+1, e, k);
}
int main()
{
int k, i;
scanf("%d %d", &n, &k);
for(i=1; i<=n; i++)
{
scanf("%d", &a[i]);
}
printf("%d", bs(1, n, k));
}
*/
/*
3004// 다시
#include <stdio.h>
int a[50001];
int b[50001];
int n, i, j, temp;
int bs(int s, int e, int k) {
int mid=(s+e)/2;
if(s>e) return 0;
if(a[mid]==k) return mid;
else if(a[mid]>k) bs(s,mid-1,k);
else bs(mid+1,e,k);
}
int swap(int t, int r) {
int p;
p=a[t];
a[t]=a[r];
a[r]=p;
}
void quicksort(int s, int e)
{
int pivot=s;
int low= pivot;
int high=e;
if(s>=e) return ;
while(low<high)
{
while(a[low]<a[pivot]) low++;
while(a[high]>a[pivot]) high--;
if(low<high) swap(low,high);
}
swap(pivot, high);
quicksort(s, high-1);
quicksort(high+1, e);
}
int main() {
int k;
scanf("%d", &n);
for(i=1; i<=n; i++) {
scanf("%d", &a[i]);
b[i]=a[i];
}
quicksort(1,n);
for(i=1; i<=n; i++) {
printf("%d ", bs(1, n, b[i])-1);
}
return 0;
}
*/
int bs에서 받을 때는 b[i]로 받는 게 아니고 그냥 정수 k로 받아야 오류 안 남.
이분탐색 활용
퀵정렬
퀵소트= void quicksort(1, 2)
pivot, low, high지정// 피봇은 맨 앞값, low=pivot, high=e; (low랑 high랑 같아지는 것 방지, 숫자가 두 개만 있을 때)
while(low<high 인 동안)
{while(low의 값이 pivot보다 작을 동안) low++;}
{while high 값이 pivot보다 클 동안 high--;}
근데 low<high되면 swap함수로 low, high 바꾸기
이후 while 나와서 pivot이랑 high 바꾸기
---------------------
피봇을 기준으로 왼쪽엔 작은 값, 오른쪽엔 큰 값 정렬 2 1 3//5//10 7
---------------------
이후 피봇이랑 (하이==왼쪽의 마지막) 서로 자리 바꾸기
---------------------
이후 재귀함수로 왼쪽도 오른쪽도 각각 정렬