7.2 顺序查找和折半查找

7.2.1 顺序查找

1.一般线性表的顺序查找

2.有序表的顺序查找

7.2.2 折半查找

右子树节点数 - 左子树节点数=0 或 1。

查找失败关键字比较次数最多为树的高度，$\left\lfloor \log_{2} n\right\rfloor +1$。

class Solution
{
public:
    int searchInsert(vector<int> &nums, int target)
    {
        int low = 0, high = nums.size() - 1;
        while (low <= high)
        {
            int mid = (low + high) / 2;

            if (nums[mid] == target)
            {
                return mid;
            }
            else if (nums[mid] < target)
            {
                low = mid + 1;
            }
            else
            {
                high = mid - 1;
            }
        }
        return low;
    }
};

7.2.3 分块查找（索引顺序查找）

索引用顺序查找或折半查找。

块内顺序查找。