Binary Search

Author Avatar
Xin Wei 4月 20, 2017
  • 在其它设备中阅读本文章

Template

    int start = 0, end = data.size() - 1;
    while (start + 1 < end)
    {
        int mid = (start + end) >> 1;
        if (...)
            ...
        else
            ...
    }
    if (...)
        return start;
    else if(...)
        return end;
    else
        return -1;

Problems

寻找第一个最大最小元素

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution
{
    public:
        int findFirstTargetPos(const vector<int> &data, int Target)
        {
            int start = 0, end = data.size() - 1;
            while (start + 1 < end)
            {
                int mid = (start + end) >> 1;
                if (data[mid] < Target)
                    start = mid;
                else
                    end = mid;
            }
            if (data[start] == Target)
                return start;
            else if(data[end] == Target)
                return end;
            else
                return -1;
            // while(start < end)
            // {
                // int mid = (start + end) / 2;
                // if (data[mid] > Target)
                    // end = mid - 1;
                // else if (data[mid] < Target)
                    // start = mid + 1;
                // else
                    // end = mid;
            // }
            // if (data[start] == Target)
                // return start;
            return -1;
        }

        int findLastTargetPos(const vector<int> &data, int target)
        {
            int start = 0, end = data.size() - 1;
            while(start + 1 < end)
            {
                int mid = (start + end) >> 1;
                if (data[mid] > target)
                    end = mid;
                else
                    start = mid;
            }
            if (data[end] == target)
                return end;
            else if (data[start] == target)
                return start;
            return -1;
        }


};

int main()
{
    vector<int> input({3,4,5,1,2,1,7,5,2,3,3,4,5,6,8});
    sort(input.begin(), input.end());
    for (int n : input)
        cout << " " << n;
    int num;
    Solution s;
    while(true)
    {
        cin >> num;
        cout << "Last Pos:" << s.findFirstTargetPos(input, num) << endl;
        cout << "First Pos:" << s.findLastTargetPos(input, num) << endl;
    }
    return 0;

}

在每一行递增,上一行最后一个元素小于下一行第一个元素的矩阵中寻找值

#include <iostream>
#include <vector>

using namespace std;

class Solution
{
    public:
        bool findMatrixElement(const vector<vector<int> > &matrix, int num)
        {
            if (matrix.empty() || matrix[0].empty())
                return false;
            int start = 0, end = matrix.size() - 1;
            while (start + 1 < end)
            {
                int mid = start + ((end - start) >> 1);
                if (matrix[mid][0] < num)
                    start = mid;
                else
                    end = mid;
            }
            int row = (matrix[end][0] <= num ? end : start);
            int new_start = 0, new_end = matrix[0].size() - 1;
            while (new_start + 1 < new_end)
            {
                int mid = new_start + ((new_end - new_start) >> 1);
                if (matrix[row][mid] < num)
                    new_start = mid;
                else
                    new_end = mid;
            }
            if (matrix[row][new_start] == num)
                return true;
            if (matrix[row][new_end] == num)
                return true;
            return false;
        }
};

int main()
{
    vector<vector<int> > input = {
        {1, 3, 5, 7},
        {10, 11, 16, 20},
        {23, 30, 34, 50}
    };
    for (vector<int> vec : input)
    {
        for (int n : vec)
            cout << n << " ";
        cout << endl;
    }
    Solution s;
    int num;
    while (cin >> num)
        cout << s.findMatrixElement(input, num) << endl;
}

寻找旋转有序序列最小值

#include <iostream>
#include <vector>

using namespace std;

class Solution
{
    public:
        int findRotateMinimum(const vector<int> &data)
        {
            int start = 0, end = data.size() - 1;
            int target = data[end - 1];
            while (start + 1 < end)
            {
                int mid = start + ((end - start) >> 1);
                if (data[mid] < target)
                    end = mid;
                else
                    start = mid;
            }
            if (data[start] < target)
                return data[start];
            else
                return data[end];
        }
};


int main()
{
    vector<int> input({4,5,6,7,0,1,2});
    for (int n : input)
        cout << n << " ";
    Solution s;
    cout << s.findRotateMinimum(input) << endl;
}