简介: 二分查找算法是针对有序数组进行查找某个元素的算法,时间复杂度为Ο(logn) 。
一、主要步骤
有序数组arr(假设从小到大),待查找元素x
(1)、直接从中间一个元素开始找,mid = (0+arr.length)/2
(2)、如果arr[mid]大于x,说明目标索引在mid索引的左半边,把左边当作一个完整的数组继续查找
(3)、如果arr[mid]小于x,说明目标索引在mid索引的右半边,把右边当作一个完整的数组继续查找
(4)、如果arr[mid]等于x,那就找到了
二、代码实现
public int search(int[] arr,int x) throws Exception{ int start = 0; int end = arr.length-1; while(start<=end){ int mid = (start+end)/2; if(arr[mid]>x){ end = mid-1; }else if(arr[mid] == x){ return mid; }else if(arr[mid]<x){ start = mid+1; } } throw new Exception("not found"+x); }
相关推荐
《数据结构与算法》-李春葆 实验报告-典型查找算法实践-二分查找、分块索引查找
二分查找算法实现-修正1
本代码是利用java语言实现基本数据查询功能,实现算法为二分查找法
数据结构用C++的实现,蓝桥杯,ACM,算法基础,C++入门
二分查找算法,二分查找算法课件,二分查找算法PPT
算法分析与设计-实验二 二分查找实验报告
二分查找算法
算法-数据结构和算法-15-二分查找.rar
算法面试通关40讲完整课件 35-36 二分查找 算法面试通关40讲完整课件 35-36 二分查找 算法面试通关40讲完整课件 35-36 二分查找 算法面试通关40讲完整课件 35-36 二分查找 算法面试通关40讲完整课件 35-36 二分查找 ...
查找算法——二分查找详解
C 语言中效率最高的查找方式,非常实用。...函数功能: 二分查找 入口参数: 待查找有序表的首地址 int *a 待查找的数据 int num 出口参数: 查找成功返回数据在有序表中的位置0 ~ n-1,不成功返回 -1
基于python的查找算法-二分查找Binary Search
二分查找算法是运用分治的典型例子:给定已按升序排好序的n个元素a[0:n-1],现要在这n个元素中找出一特定元素x。所以容易设计出二分搜索算法:在 a[0] [1] [n-1] 中搜索 x, 找到x时返回其在数组中的位置,否则返回-...
算法-理论基础- 查找- 二分查找(包含源程序).rar
//文件名:exp9-2.cpp #include #define MAXL 100 //定义表中最多记录个数 typedef int KeyType; typedef char InfoType[10]; typedef struct { KeyType key;
Java二分查找递归算法
二分查找算法是查找算法中的一种效率比较高的查找算法,对于一段数组或者字符串的查找,效率可以更高。
二分查找基于分治算法的实现