1、二分查找(binary search)
二分查找(binary search),也称折半搜索,是一种在 有序数组 中 查找某一特定元素 的搜索算法。搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空,则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。
- 时间复杂度:折半搜索每次把搜索区域减少一半,时间复杂度为O(log n)。(n代表集合中元素的个数)
- 空间复杂度: O(1)。虽以递归形式定义,但是尾递归,可改写为循环。
动图演示
二分查找
2、代码描述
递归
int binarysearch(int array[], int low, int high, int target) {
if (low > high) return -1;
int mid = low + (high - low) / 2;
if (array[mid] > target)
re服务器托管网turn binarysearch(array, low, mid - 1, target);
if (array[mid]
非递归(while循环)
int bsearchWithoutRecursion(int a[], int key) {
int low = 0;
int high = a.length - 1;
while (low key)
high = mid - 1;
else if (a[mid]
3、二分查找中值的计算
这是一个经典的话题,如何计算二分查找中的中值?大家一般给出了两种计算方法:
- 算法一:
mid = (low + high) / 2
- 算法二:
mid = low + (high – low)/2
乍看起来,算法一简洁,算法二提取之后,跟算法一没有什么区别。但是实际上,区别是存在的。算法一的做法,在极端情况下,(low + high)存在着溢出的风险,进而得到错误的mid结果,导致程序错误。而算法二能够保证计算出来的mid,一定大于low,小于high,不存在溢出的问题。
4、二分查找法的缺陷
二分查找法的O(log n)让它成为十分高效的算法。不过它的缺陷却也是那么明显的。就在它的限定之上:必须有序,我们很难保证我们的数组都是有序的。当然可以在构建数组的时候进行排序,可是又落到了第二个瓶颈上:它必须是数组。
数组读取效率是O(1),可是它的插入和删除某个元素的效率却是O(n)。因而导致构建有序数组变成低效的事情。
解决这些缺陷问题更好的方法应该是使用二叉查找树了,最好自然是自平衡二叉查找树了,既能高效的(O(n log n))构建有序元素集合,又能如同二分查找法一样快速(O(log n))的搜寻目标数。
5、练习题1
给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
请必须使用时间复杂度为O(log n)
的算法。
示例 1:
输入: nums = [1,3,5,6], target = 5
输出: 2
示例2:
输入: nums = [1,3,5,6], target = 2
输出: 1
示例 3:
输入: nums = [1,3,5,6], target = 7
输出: 4
https://leetcode.cn/problems/search-insert-position/?envType=study-plan-v2&envId=top-100-liked
>代码
class Solution {
public int searchInsert(int[] nums, int target) {
int n = nums.length;
int left=0,right=n-1;
while(left nums[mid]){
left = mid+1;
// 目标数值在中间值 左边
} else if(target
6、练习题2
给定一个 元素升序的、无重复数字的整型数组 nums和一个目标值 target,写一个函数搜索 nums中的 target,如果目标值存在返回下标(下标从 0 开始),否则返回 -1
数据范围:,数组中任意值满足
进阶:时间复杂度,空间复杂度
示例1
输入:
[-1,0,3,4,6,10,13,14],13
返回值:
6
说明:
13 出现在nu服务器托管网ms中并且下标为 6
示例2
输入:
[],3
返回值:
-1
说明:
nums为空,返回-1
>代码
import java.util.*;
public class Solution {
//nums是数组,target是目标值
public int search (int[] nums, int target) {
//定义了target在[left,right]区间内
int left = 0;
int right = nums.length-1;
//数组从小到大排序
while(right>=left){
//定义中间值的下角标
int middle = left + ((right-left)/2);
//如果中间值大于目标值,目标值在左半部分,下一轮二分查找[left,middle-1]
if (nums[middle] > target){
right = middle -1;
//如果中间值小于目标值,目标值在右半部分,下一轮二分查找[middle+1,right]
}else if(nums[middle]
7、练习题3
给定一个长度为n的数组nums,请你找到峰值并返回其索引。数组可能包含多个峰值,在这种情况下,返回任何一个所在位置即可。
1.峰值元素是指其值严格大于左右相邻值的元素。严格大于即不能有等于
如输入[2,4,1,2,7,8,4]时,会形成两个山峰,一个是索引为1,峰值为4的山峰,另一个是索引为5,峰值为8的山峰,如下图所示:
示例1
输入:
[2,4,1,2,7,8,4]
返回值:
1
说明:
4和8都是峰值元素,返回4的索引1或者8的索引5都可以
示例2
输入:
[1,2,3,1]
返回值:
2
说明:
3 是峰值元素,返回其索引 2
>代码
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net
机房租用,北京机房租用,IDC机房托管, http://www.fwqtg.net
相关推荐: 云原生微服务 第六章 Spring Cloud Eureka微服务的远程调用、负载均衡
系列文章目录 第一章 Java线程池技术应用 第二章 CountDownLatch和Semaphone的应用 第三章 Spring Cloud 简介 第四章 Spring Cloud Netflix 之 Eureka 第五章 Spring Cloud Netf…