关键词：
定义
In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array.
Binary search compares the target value to the middle element of the array;
if they are unequal, the half in which the target cannot lie is eliminated and the search continues on the remaining half until it is successful.
If the search ends with the remaining half being empty, the target is not in the array.
引用来自维基百科 Binary search algorithm
二分查找是一种搜索的算法，在有序数组中，根据目标值找到其位置。
比较目标值与数组的中间元素，如果不相等，不位于目标值的一半将会被淘汰，然后继续在另一半中搜索直到找到为止。
如果另一半中搜索是空，那么这个目标值不在数组中。
举例
比如你要登录淘宝，你的用户名叫kk，那么你登录的时候，淘宝的数据库要去搜索一下kk是否在其中，当然他不可能从a开始查起，应该从字典序的中间开始。小了，向后找，大了，向前找。
那么再举个例子，比方说，我在1 - 100 之间想一个数，你来猜，你的目标是尽可能少的次数来猜到这个数，然后我根据结果回复大了还是小了还是猜对了。
假如你从1开始递增猜，如果我想的是99，你要猜99次。
换种思路，从一半的位置开始猜，就是50，如果回复小了，那么结果就在51-100，直接排除掉前50个选项。依次进行，结果就只用7次就一定可以猜对。
我是怎么得到7次的呢，每次筛选掉一半的值
7 > log2100
所以是7次。
也就是说这个算法的效率是
O(logn)
代码
#include<iostream>
using namespace std;
int BinarySearch(int a[], int n, int element)
{
int begin = 0, last = n - 1;
int middle;
while (begin <= last)
{
middle = (begin + last) / 2;
if (element < a[middle])//查找的这个数小于中间值
last = middle - 1;
else if (element > a[middle])//查找到这个数大于中间值
begin = middle + 1;
else //相等返回索引
return middle;
}
return -1;//数组中没有这个查找的值
}
int main()
{
int n, a[100];
int digit;
cout << "请输入元素个数" << endl;
cin >> n;
cout << "请输入各元素的值" << endl;
for (int i = 0; i < n; i++)
cin >> a[i];
cout << "请输入要查找的值" << endl;
cin >> digit;
cout << "索引是";
cout << BinarySearch(a, n, digit)<<endl;
return 0;
}二分法浅谈(代码片段)
文章目录前言循环条件？当循环条件为<时当循环条件为<=时搜索的区间如何定义？溢出如何解决？前言最近在做力扣的14天计划「算法」-学习计划-力扣（LeetCode）全球极客挚爱的技术成长平台(leetcode-cn.... 查看详情
浅谈二分
这一篇blog说说二分查找其实二分我也是初学，也就是前几天才开始读课本，这几天才开始上手打代码，所以我觉得还是有点难度的，其实二分粗略的可以理解为一个你npy和你玩的一个游戏，让你猜1-1000里面的一个数，你每次告... 查看详情
浅谈二分的细节问题(代码片段)
最大值最小给定一个不降的序列(a)，求其中大于等于(x)的第一个数。其实就是查找第一个合法的点。while(l<r)mid=(l+r)>>1;if(a[mid]<x)l=mid+1;elser=mid;如果当前(mid)小了，就向右寻找，当前(mid)不可能是答案，可以直接忽略(mid)，... 查看详情
浅谈二分
大家一定对二分法有所耳闻吧！它的定义是什么？它的用途又是什么？下面我就来介绍一下二分法及其用途。引子例题找出函数(f(x)=3x-3)的零点。解法首先，找出两个数(a)，(b)，满足(a<b)且(f(a)<0)，(f(b)>0)。然后进行如下操... 查看详情
浅谈二分图(代码片段)
（一）二分图匹配给定一个二分图G，在G的一个子图M中，M的边集E中的任意两条边都不依附于同一个顶点，则称M是一个匹配。图中加粗的边是数量为2的匹配。（一）二分图判定如果一个图是连通的，可以用如下的方法判定是否... 查看详情
浅谈对二分思想的理解(代码片段)
1、什么是二分思想？二分思想可以理解为是一种将一个大问题分成两个子题，当每次分析完两个子问题后，舍弃其中一个不符合条件的子问题，再将符合条件的子问题一分为二，反复循环搜索判断的操作，直至找到所求的数值... 查看详情
整体二分浅谈
整体二分浅谈一、前置知识 在学习整体二分之前，要学会二分，以及二分的分治思想。二、整体二分浅谈及例题 例题：bzoj2527:[Poi2011]Meteors 对于这道题是整体二分的经典例题，我们先抛开整体二分，思考二分怎么做... 查看详情
浅谈二分答案的原理和相关应用(代码片段)
一、二分答案的原理和过程1.适用范围：当一个问题的解满足单调性（结果与询问数值成正相关或负相关）且待枚举数量，出现“最大值最小”或“最小值最大”等时，我们可以对答案进行二分；2.原理:1.在二分答案前，找出答... 查看详情
浅谈二分(代码片段)
太极生两仪，两仪生四象，四象生八卦，阴阳交媾万物生。若要你在全校同学当中猜我心里想的那个人，允许你问若干个问题，使问问题次数尽量少，你肯定会问我那个人是男生还是女生。因为这样，可以筛掉一半的人。并且在... 查看详情
浅谈带权二分或者斜率凸优化
APOI讲了这个东西，还有THU命题的《九省·林克卡特树》，感觉好像很热点的样子。带权二分是一类对DP的优化，对于某些最优化问题的(2d/yd)DP，通过这种优化，其效率可以达到简化后的(1d/yd)DP的效率乘一个log（(xd/yd)DP是指状... 查看详情
浅谈顺序折半查找
线性表查找的实现原理 1、线性表查找：顺序查找、折半查找。 2、顺序查找的实现思想 遍历全表，判断值是否相等，俗称蛮力法。 3、折半查找 步骤一：设置初始查找取件：left=0；right=n； ... 查看详情
网络(最大)流初步+二分图初步(浅谈ek，dinic,hungarianmethod:](代码片段)
本文中 N为点数，M为边数；EK:(brute_force)；每次bfs暴力找到一条增广路，更新流量，代码如下：时间复杂度：O(NM2)；1#include<bits/stdc++.h>2usingnamespacestd;34structnode5intnext,to,len;6edge[200005];78intval[10005],head[200005],vis[ 查看详情
二分查找(代码片段)
69.Sqrt(x)(二分查找)35.SearchInsertPosition(二分查找)34.SearchforaRange33.SearchinRotatedSortedArray(二分查找)81.SearchinRotatedSortedArrayII74.Searcha2DMatrix(二分查找，剑指offer1) 查看详情
异序二分查找二分查找方程根二分查找重复元素最后一个(代码片段)
1题目1类二分查找1.1题目将有序数组a的后面随机一段一插到数组前面，使用类似二分查找的方法，查找一个元素e。1.2解题思路将有序数组的后面一部分插到数组前面，使用二分查找查找一个元素。这样的查找，可以首先定义一... 查看详情
hiho36二分·二分查找二分查找(代码片段)
传送门:二分·二分查找分析ACCode1简洁ACCode2首先排序，然后再用原始的二分查找法，也行吧。OnlineACCode1#include<stdio.h>intmain(void)intn,k,ans=1,appeared=0,num;scanf("%d%d",&n,&k);while(n--)scanf("%d",&num);if(num<k 查看详情
二分查找+二分答案（java）
文章目录二分查找做法下标问题边界问题图解代码实现复杂度分析二分查找变形1.求满足条件的最小值(后缀)2.求满足条件的最大值(前缀)3.求最短子序列小结4.大于x的平方数5.二分浮点数二分答案常规做法引入题目小结二分查找二... 查看详情
二分查找算法
二分查找算法主要是解决在“一堆数中找出指定的数”这类问题。而想要应用二分查找法，这“一堆数”必须有一下特征：存储在数组中有序排列二分查找法的基本实现二分查找法在算法家族大类中属于“分治法”，分治法基本... 查看详情
二分查找法
二分查找法必须满足要查找的数据是有序排列的，当min>max循环结束二分查找小结： 查看详情