定义

输入：一个有序的元素列表
输出：if(包含) { return 查找元素的位置 } else { return null }
复杂度：O(「算法」二分算法 - 图1)

leetcode

  • 对应题：704. 二分查找
  • 解题：
    1. /**
    2. * @param {number[]} nums
    3. * @param {number} target
    4. * @return {number}
    5. */
    6. var search = function(nums, target) {
    7.   if (nums.length === 0 || nums[nums.length - 1] < target || nums[0] > target) {
    8.       return -1
    9.   }
    10.   if (nums[0] === target) {
    11.       return 0
    12.   }
    13.   if (nums[nums.length - 1] === target) {
    14.       return nums.length - 1 
    15.   }
    16.   var low = parseInt(nums.length / 2)
    17.   var high = nums.length - 1
    18.   while(low <= high - 1) {
    19.       if(nums[low] === target) {
    20.           return low
    21.       } else {
    22.           if (low === high -1) {
    23.               return -1
    24.           }
    25.           if(nums[low] > target) {
    26.               high = low
    27.               low = parseInt(low / 2)
    28.           } else {
    29.               low = low + parseInt((high - low) / 2)
    30.           }
    31.       }
    32.   }
    33.   return -1
    34. };