二分数组的扩展:二分查找循环有序数组

大致思路:先确定单调区间,然后根据判断指定点是否在单调区间内,剪掉另外一半区域~~如此循环。直到循环跳出,或者找到指定值对应的位置为止结束。
程序在cygwin下g++上编译通过。

#include <iostream>
#include <vector>
using namespace std;

int findPos(const vector<int>& array, int var)
{
    size_t start = 0;
    size_t end = array.size();

    while(start <= end)
    {
        int middle = start + (end - start) / 2;
        if(array[middle] >= array[start])
        {
            if(var == array[middle])
            {
                return middle;
            }
            else if(var < array[middle] && var >= array[start])
            {
                end = middle - 1;
            }
            else 
            {
                start = middle + 1;
            }
        }
        else 
        {
            if(var == array[middle])
            {
                return middle;
            }
            else if(var > array[middle] && var <= array[end])
            {
                start = middle + 1;
            }
            else
            {
                end = middle - 1;
            }
        }
    }
    return -1;
}

int main()
{
    //int Array[] = {4, 5, 1, 2, 3};
    //int Array[] = {4, 5, 1, 1, 3};
    int Array[] = {7,8,9,0,1,2,3,4,5,6};
    
    std::cout << findPos(vector<int>(Array, Array + sizeof(Array) / sizeof(int)), 9) << std::endl;
    return 0;
}




二分数组的扩展:二分查找循环有序数组

上一篇:持久化persistence.xml配置文件


下一篇:让你的页面不在刷新(F5,右键都不好使)