循环有序数组的二分查找

cycle-binary-search.js

/**
* @synopsis  二分法搜索循环有序数组 
*
* @param s 要查找的数组
* @param k 要查找的关键字
*
* @returns 当 k 存在时返回 k 的下标，当 k 不存在时返回 -1
*/
var foo = function (s, k) {
    var mid;
    var l = 0;
    var r = s.length - 1;
    while (l <= r) {
        mid = parseInt((l + r) / 2);
        if (k == s[mid]) {
            return mid;
        } else if (k < s[mid]) {
            if (s[l] < s[mid] && k >= s[l]) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        } else if (k > s[mid]) {
            if (s[r] > s[mid] && k <= s[r]) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
    }
    return -1;
};

for (var i = -1; i <= 10; i++) {
    console.log(foo([5, 6, 7, 8, 9, 0, 1, 2, 3, 4], i));
    // 输出 -1 5 6 7 8 9 0 1 2 3 4 -1
}