查找效率满分的算法—— “二分查找” 算法（Java版）_java二分查找算法

技术文档

本篇会加入个人的所谓鱼式疯言

❤️❤️❤️鱼式疯言:❤️❤️❤️此疯言非彼疯言

而是理解过并总结出来通俗易懂的大白话,

小编会尽可能的在每个概念后插入鱼式疯言,帮助大家理解的.

🤭🤭🤭可能说的不是那么严谨.但小编初心是能让更多人能接受我们这个概念 ！！！

查找效率满分的算法—— “二分查找” 算法（Java版）_java二分查找算法

前言

在前面的章节中，我们学习了 \"双指针\"算法 ， “滑动窗口\"算法

而在本篇章节，我们期待已久的 “二分查找”算法 即将登场，透露下本次算法主要的规划 💖 💖 💖

一. 二分算法的初识

1. 二分算法的简介

二分算法，也被称为二分查找算法，是一种常用的查找 算法。

它的基本思想是将已排序的数据序列分成 两部分 ，取中间的元素与 目标值 进行比较，然后根据比较结果，确定目标值在左半部分还是右半部分，再继续在相应的部分进行 查找，直到找到目标值或者确定目标值不存在为止。

2. 二分算法的使用步骤

因为二分查找算法分为两种：

“一种是朴素二分查找” 算法，另外一种是 \"左右边界二分查找 \" 算法

因为朴素二分查找比较基础，我们先学习基础版本的，再调整有难度的 💖 💖 💖

小编在这里说明 “朴素二分查找” 的具体步骤哦

先拿个题目来瞧瞧呗

二分查找

704.二分查找题目链接

. 题目描述

查找效率满分的算法—— “二分查找” 算法（Java版）_java二分查找算法

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

题目含义

在给定的数组中查找一个数，返回其下标，如果没有就返回 -1

. 讲解算法思想

题目分析：我们要查找一个数最简单的方式

解法一 ：

暴力求解

用一个 for -遍历数组，然后中间用一个 if 来判断，一定成立就返回其下标

在解法一的基础上，我们为了减少一半的数据，特别提炼出 二分查找 算法的思想

解法二 ：

二分算法 :

查找效率满分的算法—— “二分查找” 算法（Java版）_java二分查找算法

首先，确定要查找的目标值在序列中的可能范围，通常是通过比较目标值和序列的 第一个元素 和 最后一个元素 来确定；

我们定义一个数组的第一个元素的为 left ，再定义最后一个元素的下标为 right

然后，在可能范围内，取中间的元素与目标值进行比较；
如果中间的元素等于目标值，则查找成功，返回对应的位置；
如果中间的元素 大于 目标值，则说明目标值可能在左半部分，缩小范围到 左半部分 继续查找，重复步骤2；
如果中间的元素 小于 目标值，则说明目标值可能在右半部分，缩小范围到 右半部分 继续查找，重复步骤2；
如果范围缩小到只有一个元素，但该元素不等于目标值，则查找失败，目标值不存在。
二分算法的时间复杂度为 O(log n) ，其中 n是序列的长度。``二分算法通常适用于已排序的数据序列，能够 快速查找目标值 的位置。

. 编写代码

class Solution {  public int search(int[] nums, int target) {  int numslen = nums.length; int left=0,right=numslen-1; while(left <= right) {  int mid= left + ((right - left) >>> 1); if(nums[mid] > target) {  right = mid - 1; } else if(nums[mid] < target ) {  left = mid + 1; } else {  return mid; } } return -1; }}

查找效率满分的算法—— “二分查找” 算法（Java版）_java二分查找算法

鱼式疯言

朴素二分的算法体会就是

小了 整体新的区间移动到 中间值的右边

大了 整体新的区间移动到 中间值的左边

并且

查找效率满分的算法—— “二分查找” 算法（Java版）_java二分查找算法

前言

目录