LintCode 14. 二分查找 JavaScript算法

描述

给定一个排序的整数数组（升序）和一个要查找的整数target，用O(logn)的时间查找到target第一次出现的下标（从0开始），如果target不存在于数组中，返回-1。

样例

- 样例  1:
	输入:[1,4,4,5,7,7,8,9,9,10]，1
	输出: 0
	
	样例解释: 第一次出现在第0个位置。

- 样例 2:
	输入: [1, 2, 3, 3, 4, 5, 10]，3
	输出: 2
	
	样例解释: 第一次出现在第2个位置
	
- 样例 3:
	输入: [1, 2, 3, 3, 4, 5, 10]，6
	输出: -1
	
	样例解释: 没有出现过6， 返回-1

二分查找是一种基于比较目标值和数组中间元素的教科书式算法。

如果目标值等于中间元素，则找到目标值。
如果目标值较小，继续在左侧搜索。
如果目标值较大，则继续在右侧搜索。

算法：

初始化指针 left = 0, right = n - 1。
当 left <= right：
比较中间元素 nums[pivot] 和目标值 target 。
如果 target = nums[pivot]，返回 pivot。
如果 target < nums[pivot]，则在左侧继续搜索 right = pivot - 1。
如果 target > nums[pivot]，则在右侧继续搜索 left = pivot + 1。

二分法代码：

const binarySearch = function (nums, target) {
    var left, right, mid, res;
    res = 0;
    left = 0;
    right = nums.length - 1;
    while (left <= right) {
        mid = Math.floor((left + right) / 2);
        if (nums[mid] === target) {
            res = mid;
        }
        if (nums[mid] >= target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    if (nums[res] != target) {
        return -1;
    }
    return res;
}

快速查找代码

const binarySearch = function (nums, target) {
    m=nums.indexOf(target);
    if(m===null) return -1;
    else return m;
}

运行结果