python面试题- 【二分法查找】给定一个已排序的非重复整数数组和一个目标值,如果找到目标,则返回索引。

前言

在给定非重复整数的排序数组和目标值的情况下,如果找到目标,则返回索引。如果不是,则返回顺序插入索引的位置。

[En]

Given a sorted array of non-repeating integers and a target value, if the target is found, the index is returned. If not, returns the position where the index was inserted sequentially.

题目

在给定非重复整数的排序数组和目标值的情况下,如果找到目标,则返回索引。如果不是,则返回顺序插入索引的位置。

[En]

Given a sorted array of non-repeating integers and a target value, if the target is found, the index is returned. If not, returns the position where the index was inserted sequentially.

(用二分法寻找和解决)

[En]

(find and solve by dichotomy)

例1:

[En]

Example 1:

输入: [1,3,5,6], 5
输出:2

[En]

Output: 2

示例2:

[En]

Example 2:

输入: [1,3,5,6], 2
输出:1

[En]

Output: 1

示例3:

[En]

Example 3:

输入: [1,3,5,6], 7
输出:4

[En]

Output: 4

示例4:

[En]

Example 4:

输入: [1,3,5,6], 0
输出:0

[En]

Output: 0

二分法查找

二分搜索,也被称为二分搜索(Binary Search),是一种更有效的搜索方法。但是,二进制搜索必须是有序数组。

[En]

Binary search, also known as half search (Binary Search), is a more efficient search method. However, the binary search must be an ordered array.

二分法思想

[En]

Dichotomy thought

1.首先从数组的中间元素开始查找,如果该元素正好是目标元素,则搜索结束,否则执行下一步。
2.如果目标元素大于/小于中间元素,则在数组大于/小于中间元素的那一半区域查找,然后重复步骤1的操作。
3.如果某一步数组为空,则表示找不到目标元素

如下图所示,数组中有目标元素,查找21

[En]

As shown in the following figure, there are target elements in the array, look for 21

python面试题- 【二分法查找】给定一个已排序的非重复整数数组和一个目标值,如果找到目标,则返回索引。

如下图所示,数组中没有目标元素,请查看70

[En]

As shown in the following figure, there are no target elements in the array, look for 70

python面试题- 【二分法查找】给定一个已排序的非重复整数数组和一个目标值,如果找到目标,则返回索引。

直到低>高查找失败

[En]

Until the low > high lookup fails

python面试题- 【二分法查找】给定一个已排序的非重复整数数组和一个目标值,如果找到目标,则返回索引。

python3 二分法查找

python3 代码示例

from typing import List

class Solution:
"""
    二分法查找
"""
    def searchInsert(self, nums: List[int], target: int) -> int:
        low, high = 0, len(nums) - 1
        while low <= 1 2 high: mid="low" + (high-low) if nums[mid]="=" target: return elif < low="mid" else: high="mid" - # 没找到则返回其位置左边的下标, 即为它按顺序插入的位置 __name__="=" '__main__': res1="Solution().searchInsert([1," 3, 5, 6], 5) print(res1) res2="Solution().searchInsert([1," 7) print(res2) code></=>

举一个目标值为7的例子

[En]

Take an example with a target value of 7

在第一轮比对中,MID的中间位置是数字3。

[En]

In the first round of comparison, the middle position of mid is the number 3.

python面试题- 【二分法查找】给定一个已排序的非重复整数数组和一个目标值,如果找到目标,则返回索引。

target目标值7 大于中间数字3,所以第二轮比较

python面试题- 【二分法查找】给定一个已排序的非重复整数数组和一个目标值,如果找到目标,则返回索引。

target目标值7 大于中间数字5,所以第三轮比较

python面试题- 【二分法查找】给定一个已排序的非重复整数数组和一个目标值,如果找到目标,则返回索引。

由于第三轮比较target目标值7 大于中间数字6,此时low=mid=high了,依然满足 while low <= high< code>,&#x6240;&#x4EE5;&#x8FD8;&#x4F1A;&#x6709;&#x4E0B;&#x4E00;&#x8F6E;&#x6BD4;&#x8F83;<br>&#x6B64;&#x65F6;<code>low = mid + 1</code> &#x5FAA;&#x73AF;&#x7ED3;&#x675F;&#xFF0C;&#x6700;&#x7EC8;&#x8FD4;&#x56DE;&#x5DE6;&#x8FB9;&#x7684;&#x4E0B;&#x6807; low<br><img src="https://img2022.cnblogs.com/blog/1070438/202207/1070438-20220712225310170-1046745312.png"><!--=-->

参考博客https://blog.csdn.net/weixin_43511031/article/details/122494815

Original: https://www.cnblogs.com/yoyoketang/p/16472052.html
Author: 上海-悠悠
Title: python面试题- 【二分法查找】给定一个已排序的非重复整数数组和一个目标值,如果找到目标,则返回索引。

原创文章受到原创版权保护。转载请注明出处:https://www.johngo689.com/6344/

转载文章受原作者版权保护。转载请注明原作者出处!

(0)

大家都在看

发表回复

登录后才能评论
免费咨询
免费咨询
扫码关注
扫码关注
联系站长

站长Johngo!

大数据和算法重度研究者!

持续产出大数据、算法、LeetCode干货,以及业界好资源!

2022012703491714

微信来撩,免费咨询:xiaozhu_tec

分享本页
返回顶部