算法(Java实现)—— 二分搜索算法
2024-10-20 15:56:58
二分搜索算法
有序数列才可用二分查找算法
思路分析
思路分析
首先确定该数组的中间下标mid = (left + right)/ 2
然后让需要查找的数findVal和arr【mid】比较
findVal > arr[mid],向右查询
findVal < arr[mid],向右查询
findVal == arr[mid],找到,返回
结束递归的条件
找到就结束
递归完整个数组,未找到,结束递归,left > right
二分查找递归算法
基本写法
public static int binarySearch(int[] arr,int left,int right,int findVal){
if (left > right){
return -1;
}
//确定中间数组的下标
int mid = (left + right)/2;
int midVal = arr[mid];
//与中间数组比较
if (findVal > midVal){//向右查找
return binarySearch(arr,mid+1,right,findVal);
}else if (findVal < midVal){
return binarySearch(arr,left,mid-1,findVal);
}else {
return mid;
}
}
新需求
当一个数组中有多个相同的数值是 ,将所有数值都查到
代码实现
package com.why.search;
import com.sun.jdi.PathSearchingVirtualMachine;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.ListIterator;
import java.util.logging.Level;
/**
* @Description TODO 当一个数组中有多个相同的数值是 ,将所有数值都查到,使用二分查找
* @Author why
* @Date 2020/11/1 16:35
* Version 1.0
**/
public class NewBinarySearch {
public static void main(String[] args) {
int[] arr = {1,8,8,10,10,10,10,11};
List res = newBinarySearch(arr, 0, arr.length - 1, 8);
if (!res.isEmpty()){
System.out.println(res);
}else {
System.out.println("未找到");
}
}
/**
* 二分查找查找多条数据
*
* 思路:
* 找到mid值时,不要马上返回
* 向mid 索引值的左边扫描将所有满足查找值的元素下标加入到集合
* 向右扫描将所有满足查找值的元素下标加入到集合
* @param arr
* @param left
* @param right
* @param findVal
* @return
*/
public static List<Integer> newBinarySearch(int[] arr, int left, int right, int findVal){
if (left > right){
return new ArrayList<Integer>();
}
int mid = (left + right) / 2;
int midVal = arr[mid];
if (findVal > midVal){
return newBinarySearch(arr,mid + 1,right,findVal);
}else if (findVal < midVal){
return newBinarySearch(arr,left,mid - 1,findVal);
}else {
List<Integer> resIndexList = new ArrayList<>();
//向左边扫描
int temp = mid - 1;
while (true){
if (temp < 0 || arr[temp] != findVal){
break;
}
resIndexList.add(temp);
temp -= 1;
}
//中间值
resIndexList.add(mid);
//向右扫描
temp = mid + 1;
while (true){
if (temp > arr.length || arr[temp] != findVal){
break;
}
resIndexList.add(temp);
temp += 1;
}
return resIndexList;
}
}
}
二分查找非递归算法
需求
数组{1,3,8,10,11,67,100},编程实现二分查找,以非递归形式完成
代码实现
package whyAlgorithm.binaryseaech;
import jdk.swing.interop.LightweightFrameWrapper;
/**
* @Description TODO 二分查找非递归形式
* @Author why
* @Date 2020/12/9 19:53
* Version 1.0
**/
public class BinarySearchNoRecursion {
public static void main(String[] args) {
int[] arr = {1,3,8,10,11,67,100};
int target = binarySearch(arr,10);
System.out.println("下标:" + target);
System.out.println(arr[target]);
}
/**
* 二分查找非递归算法
* @param arr 数组,升序排列
* @param target 需要查找的算法
* @return 返回数组下标
*/
public static int binarySearch(int[] arr,int target){
int left = 0;
int right = arr.length - 1;
while (left <= right){//查找
int mid = (left + right)/2;
if (arr[mid] == target){//找到中间数
return mid;
}else if (arr[mid] > target){//大于向左查找
right = mid - 1;
}else {//小于向右查找
left = mid + 1;
}
}
return -1;
}
}
最新文章
- 实现UniqueAttribute唯一性约束,sqlunique约束[转]
- Boo who
- Android IOS WebRTC 音视频开发总结(七)-- 基于浏览器的开发
- tmux与vim主题不一致
- Codeforces Round #198 (Div. 2) C. Tourist Problem (数学+dp)
- Java Reflection(getXXX和getDeclaredXXX)
- 还能不能愉快地起一个web服务啦?——1st Step!白话http和代码交互的那点儿事儿~
- form,ajax注册,logging日志使用
- leetcode34
- 洛谷 P1378 油滴扩展 改错
- 接口app 接口中上传 图片
- np.tile语法
- Oracle sys 用户无密码文件无法登录
- python的re正则表达式模块
- 【Android】Retrofit网络请求Service,@Path、@Query、@QueryMap...
- 初学者浅谈我对领域驱动设计(DDD)的理解
- Comparable<;T>; 和 Comparator<;T>;
- 深入理解Java虚拟机---类加载机制(简略版)
- IntelliJ Idea编译报错:javacTask: 源发行版 1.8 需要目标发行版 1.8
- hdu 5207 Greatest Greatest Common Divisor 数学