카테고리 없음

binary search 응용

fw93 2018. 3. 26. 18:33
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include "stdafx.h"
#include <iostream>
#include <vector>
 
using namespace std;
 
int bsearch(vector<int> * data, int x, int low, int high) {
    if (low == high) {
        if (x == data->at(low)) return low;
        else return -1;
    }
    int mid = (low + high) / 2;
    if (data->at(mid) == x) {
        return mid;
    }
    else if (data->at(mid) > x) {
        return bsearch(data, x, low, mid);
    }
    else {
        return bsearch(data, x, mid + 1, high);
    }
}
 
int findmin(vector<int> * data, int low, int high) {
    cout << low << " " << high << endl;
    if (high - low == 1) {
        return data->at(low) > data->at(high) ? high : low;
 
    }
    int mid = (low + high) / 2;
    if (data->at(low) > data->at(mid) && data->at(mid)<data->at(high)) {
        return findmin(data, low, mid);
    }
    else if(data->at(low)<data->at(mid)&&data->at(mid)>data->at(high)){
        return findmin(data, mid, high);
    }
    else if(data->at(low)<data->at(mid)&&data->at(mid)<data->at(high)){
        return low;
    }
    else if (data->at(low) == data->at(mid) && data->at(mid) == data->at(high)) {
        return low;
    }
    else if (data->at(low) == data->at(mid) && data->at(mid) > data->at(high)) {
        return findmin(data, mid, high);
    }
    else if (data->at(low) > data->at(high) && data->at(mid) == data->at(high)) {
        return findmin(data, low, mid);
    }
    else {
        return low;
    }
}
 
int findx(vector<int> * data, int x, int low, int high) {
    //base case
    if (low == high - 1) {
        if (data->at(low) == x) {
            return low;
        }
        else if (data->at(high) == x) {
            return high;
        }
        else {
            return -1;
        }
    }
    //check if recursion needed
    int mid = (low + high) / 2;
    if (data->at(mid) == x) {
        return mid;
    }
    if (data->at(low) <= data->at(mid)) {
        if (x >= data->at(low) && x <= data->at(mid)) {
            return findx(data, x, low, mid);
        }
    }
    else {
        if (x <= data->at(mid) && x >= data->at(low)) {
            return findx(data, x, low, mid);
        }
    }
    if (data->at(mid) <= data->at(high)) {
        if (x >= data->at(mid) && x <= data->at(high)) {
            return findx(data, x, mid, high);
        }
    }
    else {
        if (x >= data->at(mid) && x <= data->at(high)) {
            return findx(data, x, mid, high);
        }
    }
    //if else crash (found edge case)
    return -9999;
}
 
 
int main() {
    vector<int> v1 = { 1,1,1,1,1,2,3,4,5 }; // { 7,9,11,14,17,18,19,20,1,3,4,5 };
    cout << v1.at(findx(&v1,2, 0, v1.size() - 1)) << endl;;
    while(1){ }
    return 0;
}
cs


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
int findstring(vector<string> * data, string target, int low, int high){
    // base cases
    if(low>high){
        return -1;
    }
    if(low==high){
        if(target==data->at(low)){
            return low;
        }else{
            return -1;
    }
 
    int mid = (low+high)/2;
    // find first interation with an unempty string
int tl = mid;
    int th = mid;
    int flag = 0;
    while(tl>=low && th<=high){
        if(data->at(tl).size()!=0){
            flag+=1;
break;
        }
        if(data->at(th).size()!=0){
            flag+=2;
            break;
        }
        tl--;
        th++;
    }
    // completly empty, return -1
    //if(tl<0 && th>=data-.size()) return -1;
    int pivot;
    // consider known empty slots while iteating tl and th
    if(flag==2){
        if(data->at(th)==target) return th;
        if(data->at(th)>target) return findstring(data,target,low,tl-1);
        else return findstring(data,target,th+1,high);
    }else if(flag==1){
        if(data->at(tl)==target) return tl;
        if(data->at(tl)>target) return findstring(data,target,th,high);
        else return findstring(data,target,low,tl-1);
    }else{
        return -1;
    }
}
 
cs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
int findclosest(int ref, unordered_multimap<string, int>::iterator low, unordered_multimap<string, int>::iterator high, int dist) {
    if (dist <= 3) {
        int min = INT_MAX;
        while (low != high) {
            int tmp = abs(low->second - ref);
            if (tmp < min) min = tmp;
            low++;
        }
        return min;
    }
    auto mid = low;
    advance(low, dist / 2);
    mid++;
    int disth = abs(ref - mid->second);
    mid--;
    int distm = abs(ref - mid->second);
    mid--;
    int distl = abs(ref - mid->second);
    mid++;
    if (distm - distl >= 0) {
        mid++;
        return findclosest(ref, low, mid, dist / 2 + 1);
    }
    else if (distm - disth >= 0) {
        return findclosest(ref, mid, high, dist - dist / 2);
    }
    else {
        return distm;
    }
}
cs


저작자표시 (새창열림)