黑马程序员Java面试宝典（完整版）

2021黑马程序员Java面试宝典笔记（完整版）

哔哩哔哩视频资源链接：https://www.bilibili.com/video/BV15b4y117RJ?spm_id_from=333.337.search-card.all.click&vd_source=7c5f1f4c039688f19024d50ef51aaed1

一、基础篇

1. 二分查找

要求

• 会用个人的语言来详细说明二分查找算法的基本原理及其实现步骤
• 会编写二分查找法的代码实现，并理解其时间复杂度分析
• 熟练掌握如何解答各种变形题型中的二分查找问题

算法描述

前提：有已排序数组 A（假设已经做好）

定义左边界 L、右边界 R，确定搜索范围，循环执行二分查找（3、4两步）

获取中间索引 M = Floor((L+R) /2)

中间索引的值 A[M] 与待搜索的值 T 进行比较

① A[M] == T 表示找到，返回中间索引

A[M] > T时，在其他右侧元素均超过T的情况下，在中间索引左侧进行查找，并将右边界设为M−1的位置后重新执行查找过程

A[M] < T时，则表示左边的所有元素均小于T值；无需进行比较操作即可确定目标位置位于右侧区域；将当前中间索引+1作为新的左边