Skip to content

binary-search.md

Latest commit

 

History

History
183 lines (137 loc) · 5 KB

binary-search.md

File metadata and controls

183 lines (137 loc) · 5 KB

704. Binary Search - 二分查找

Tags - 题目标签

Description - 题目描述

EN:

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.

 

Example 1:

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4

Example 2:

Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1

 

Constraints:

  • 1 <= nums.length <= 104
  • -104 < nums[i], target < 104
  • All the integers in nums are unique.
  • nums is sorted in ascending order.

ZH-CN:

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。


示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

 

提示：

  1. 你可以假设 nums 中的所有元素是不重复的。
  2. n 将在 [1, 10000]之间。
  3. nums 的每个元素都将在 [-9999, 9999]之间。

Link - 题目链接

LeetCode - LeetCode-CN

Latest Accepted Submissions - 最近一次 AC 的提交

Language Runtime Memory Submission Time
typescript 84 ms 41.9 MB 2021/04/08 0:48 
function search(nums: number[], target: number): number {
  // 找下界：
  // let left  = 0; 
  // let right = nums.length - 1;

  // while (left <= right) {
  //   let mid = left + Math.floor((right - left)/2);
  //   if (nums[mid] >= target) {
  //     // 找满足 x >= target 的第一个元素(下界)
  //     right = mid - 1;
  //   } else {
  //     left = mid + 1;
  //   }   
  // }
  // // 判断一下是否越界，或者不相等
  // if (left >= nums.length || nums[left] !== target) {
  //   // 找到下界后，判断是否存在
  //   return -1;
  // }

  // return left;

  // 找上界：
  let left  = 0; 
  let right = nums.length - 1;

  while (left <= right) {
    let mid = left + Math.floor((right - left)/2);
    if (nums[mid] > target) {
      // 找满足 x <= target 的最后一个元素(上界)
      right = mid - 1;
    } else {
      left = mid + 1;
    }   
  }
  // 判断一下是否越界，或者不相等
  if (right< 0 || nums[right] !== target) {
    // 找到下界后，判断是否存在
    return -1;
  }

  return right;
  
};

My Notes - 我的笔记

两种思路

找下界(以此为准)

let left  = 0; 
  let right = nums.length - 1;

  while (left <= right) {
    let mid = left + Math.floor((right - left)/2);
    if (nums[mid] >= target) {
      // 找满足 nums[mid] >= target 的第一个元素(下界)
      right = mid - 1;
    } else {
      left = mid + 1;
    }   
  }
  // 判断一下是否越界，或者不相等
  if (left >= nums.length || nums[left] !== target) {
    // 找到下界后，判断是否存在
    return -1;
  }

  return left;

找上界

  let left  = 0; 
  let right = nums.length - 1;

  while (left <= right) {
    let mid = left + Math.floor((right - left)/2);
    if (nums[mid] <= target) {
			 left = mid + 1;
      // 找满足 x <= target 的最后一个元素(上界)
    } else {
			right = mid - 1;
    }   
  }
  // 判断一下是否越界，或者不相等
  if (right< 0 || nums[right] !== target) {
    // 找到下界后，判断是否存在
    return -1;
  }

  return right;

参考