代码随想录-数组

数据结构学习记录，部分图片来自于代码随想录，侵权删~

一、数组的基本概念

  • 数组是存放在连续内存空间上的相同类型数据的集合。

  • 可以通过下标索引的方式获取到下标下对应的数据。算法通关数组

  • 数组下标都是从0开始的。

  • 数组内存空间的地址都是连续的，因此删除某个元素之后就需要将该元素后的所有元素都要做移动操作。算法通关数组1

  • 数组的元素是不能删的，只能覆盖。

  • 二维数据的地址不一定是连续的，不同语言的设计原理不同。算法通关数组2

二、二分查找

Leetcode题目链接 704.二分查找

思路

前提：

  1. 有序数组
  2. 数组中无重复元素

主要问题是区间的定义问题：

代码

Go版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func search(nums []int, target int) int {
    left,right := 0, len(nums)-1
    for left <= right{
        mid := (right - left)/2 + left
        num := nums[mid]
        if num == target {
            return mid
        }else if num > target {
            right =  mid -1
        }else{
            left = mid + 1
        }
    }
    return -1
}

Python 版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left  = 0
        right = len(nums)-1
        while left <= right:
            mid = (right - left) // 2 + left
            num = nums[mid]
            if num == target:
                return mid
            elif num > target:
                right = mid - 1
            else:
                left = mid + 1
        return -1