LinkedIn 面试题 （2013.12.09）：部分排序数组找值

本文主要是介绍LinkedIn 面试题 （2013.12.09）：部分排序数组找值，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：整数数组，部分排序，如 [9, 11, 1, 3, 6, 7]， 给定某个query，如果query存在数组，返回index，否则返回-1。

题解：

class Solution {
public:int FindInteger(int* array, const int query, const int start, const int end) {int index = -1;assert(array != nullptr);int middle = start + (end - start)/2;if(array[start] < array[middle]){if(array[start] <= query && array[end] >= query)index =  BinarySearch(array, start, middle, query);elseindex =  FindInteger(array, query, middle+1, end);}else{if(array[middle] <= query && query <= array[end])index =  BinarySearch(array, middle, end, query);elseindex = FindInteger(array, query, start, middle-1);}return index;}private:static int BinarySearch(int* array, int start, int end, int query){if(start > end)return -1;int middle = start + (end-start)/2;if(array[middle] == query)return middle;else if(array[middle] < query )return BinarySearch(array, middle+1, end, query);elsereturn BinarySearch(array, start, middle-1, query);    }
};

测试用例：

#include <cassert>
#include <iostream>using namespace std;int main(int argc, char* argv[])
{int Array[6] = {9, 11, 1, 3, 6, 7};Solution s;cout << s.FindInteger(Array, 1, 0, 5) << endl;return 0;
}

这篇关于LinkedIn 面试题 （2013.12.09）：部分排序数组找值的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---