在alternatively sorted的数组中查找元素

组中查找元素"/>

在alternatively sorted的数组中查找元素

这里alternatively sorted的数组是指 奇数位置index上的数升序排列 与 偶数位置index上的数升序排列

如12,2,16,5,18,32,33,38

用2次二分查找就可以达到要求

/*
Given an array which is alternatively sorted. Find an element in it.
e.g. 12,2,16,5,18,32,33,38
*/
#include <algorithm>
#include <iostream>int binarySearch(int* a, int left, int right, int target)
{if(left <= right){if(target > a[right] || target < a[left])return -1;int mid = (left + right) / 2;if(mid - left == 1 && right - mid == 1)return -1;if(a[mid] == target)return mid;else if(a[mid] > target)return binarySearch(a, left, mid - 2, target);elsereturn binarySearch(a, mid + 2, right, target);}
};int findElemIdx(int* a, int n, int target)
{if(n == 0)return -1;else if(n == 1){if(target == a[0])return 0;elsereturn -1;}else{int endIdx = n - 1;int res;int oddIdx, evenIdx;if(endIdx % 2 == 1){oddIdx = endIdx;evenIdx = endIdx - 1;}else{evenIdx = endIdx;oddIdx = endIdx - 1;}res = binarySearch(a, 1, oddIdx, target);if(res == -1)res = binarySearch(a, 0, evenIdx, target);return res;}
};int main()
{int a[] = {12,2,16,5,18,32,33,38};int res = findElemIdx(a, 8, 2);return 0;
}