二分查找

• 1.题目
• • 1.1中文
  • 1.2英文
• 2.算法思想
• 3.代码运行
• • 3.1 javascript
  • 3.2 Python3
• 4 小拓展
• • 4.1 js中的可除运算
  • 4.2 python3中的可除运算

1.题目

1.1中文

给定一个 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.2英文

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.

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

2.算法思想

按升序排列nums 在中查找目标值 target
1.在js中有 nums.indexOf(target) ,可以直接找到下标对应的目标值，不会返回no。-1
2.二进制查找算法的原理如下：
要调查的顺序：nums; 目标值： target

1. 如果nums为空，然后返回-1然后退出；target。
2. 如果nums如果它不为空，请将其中间元素与要查找的目标元素匹配，以查看它们是否相等。
3. 如果相等，则返回中间元素的索引，然后返回并退出。
4. 如果它们不相等，请比较两个元素的大小。
5. 如果该 中间元素 大于 目标元素 ， [low,height] = [low,mid-1]
6. 如果该 中间元素 小于 目标元素 ， [low,height] = [mid+1,height]
7. 在要调查的新序列上重新启动第一个。1工作步骤。
   二进制查找很快，因为每次匹配不成功时，它都会排除剩余元素的一半。因此，可能包含目标元素的有效范围会迅速缩小，而不是像顺序查找那样一次只排除一个元素。

3.代码运行

3.1 javascript

//这里没有算法。
var search = function(nums, target) {
       return nums.indexOf(target)
};

var search = function(nums, target) {
        let low=0 ,height=nums.length-1
        while (low<=height){
            let mid= Math.floor((height-low)/2)+low
            if(nums[mid]==target){
                return mid
            }else if(nums[mid]>target){
                height=mid-1
            }else{
                low=mid+1
            }
        }
        return -1
};

3.2 Python3

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        low,height=0,len(nums)-1
        while low<=height:
            mid=(height-low)//2+low
            if nums[mid]==target:
                return mid
            elif nums[mid]>target:
                height=mid-1
            else:
                low=mid+1
        return -1

4 小拓展

4.1 js中的可除运算

  Math.ceil(4/3); //向上整除 4/3=2;
  Math.floor(4/3); //向下整除 4/3=1;
  Math.round(5/2);//四舍五入  parseInt(5/2);//丢弃分数部分,保留整数部分

4.2 python3中的可除运算

(height-low)//2