数组01–二分查找

1. 数组的基本理论

• 数组下标从0开始；
• 数组内存空间连续；
  • 导致数组增加和删除元素需要移动其他元素，开销很大！
  • vector 和 array 的区别：
    • vector 的底层是用array实现的，所以，vector是容器，而不是数组！
  • 数组的元素是不能删除的，只能覆盖！
• 二维数组的内存地址一般是连续的，可能不同，C++是连续的；
• 测试二维数组的内存地址空间是否连续：

# include <iostream>
using namespace std;
void test_arr() {
    int array[2][3] = {
        {0, 1, 2},
        {3, 4, 5}
    };
    cout << &array[0][0] << " " << &array[0][1] << " " << &array[0][2] << endl;
    cout << &array[1][0] << " " << &array[1][1] << " " << &array[1][2] << endl;
}

int main() {
    test_arr();
}

2. 二分查找

704 Binary Search

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.

经典二分查找的模板：

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;  //定义target在左闭右闭空间[left, right]

        while(left <= right){  // 因为left==right时，闭区间依然有效
            int middle = left + ((right - left) / 2);  // 防止溢出
            if (nums[middle] > target) {
                right = middle - 1;
            }else if (nums[middle] < target) {
                left = middle + 1;
            } else {
                return middle;
            }
        }
        return -1;        
    }
};

C语言写法：

int search(int* nums, int numsSize, int target){
    int left = 0, right = numsSize -1;    
    while(left <= right) {
        int middle = (left + right)/2;
        if (target < nums[middle]) {
            right = middle - 1;
        } else if (target > nums[middle]) {
            left = middle + 1;
        } else {
            return middle;
        }
    }
    return -1;
}

二分查找的第二种方法

• 第一种写法是左闭右闭区间，这里考虑改成左闭右开区间[left, right)
• 这样，判断的边界条件就发生了变化；

如下两点：

• while (left < right)，这里使用 < ,因为left == right在区间[left, right)是没有意义的 if (nums[middle] > target) right 更新为 middle，因为当前nums[middle]不等于target，去左区间继续寻找，而寻找区间是左闭右开区间，所以right更新为middle，即：下一个查询区间不会去比较nums[middle]

总结

• 二分查找最重要的地方，是搞清3点!
  1. 根本点： 使用闭区间还是开区间；
  2. while中的条件在该区间下是否存在；
  3. 闭区间的right是middle-1，开区间的right是middle；但是left都是middle+1；因为开区间的时候，middle为right就刚好是取不到的情况！

其他相关题目

• 35
• 34
• 69
• 367