查找算法(1)--二分查找
查找算法(1)--二分查找
haoran_10 发表于1年前
查找算法(1)--二分查找
  • 发表于 1年前
  • 阅读 18
  • 收藏 0
  • 点赞 0
  • 评论 0

简介:  二分查找算法是针对有序数组进行查找某个元素的算法,时间复杂度为Ο(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);
}

 

标签: 二分查找
共有 人打赏支持
粉丝 27
博文 88
码字总数 80846
×
haoran_10
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: