您现在的位置是：首页 > 后台技术 > 数据结构与算法数据结构与算法

二分查找算法(图文)

第十三双眼睛2023-10-18【数据结构与算法】人已围观

简介二分查找算法

二分查找算法，找到一个下标就返回

package com.xingchen.day007;
public class BinSearch {
// 使用二分法查找数据的前提是数组是有序的
public static void main(String[] args) {
int[] arr = {1,8,10,89,1000,1234};
int i = binSearch(arr,0,arr.length,89);
System.out.println(i);
}
public static int binSearch(int[] arr, int left,int right,int findValue) {
if (left > right) {
return -1;
}
int mid = (left + right) / 2;
int midValue = arr[mid];
if (findValue > midValue) {
return binSearch(arr,mid+1,right,findValue);
} else if(findValue < midValue){
return binSearch(arr,left,mid-1,findValue);
}else {
return mid;
}
}
}

改进：返回全部的索引

package com.xingchen.day007;
import java.util.ArrayList;
import java.util.List;
public class BinSearch {
// 使用二分法查找数据的前提是数组是有序的
public static void main(String[] args) {
int[] arr = {1,8,10,89,1000,1000,1000,1000,1234};
List<Integer> list = binSearch(arr,0,arr.length,1000);
System.out.println(list.toString());
}
public static List<Integer> binSearch(int[] arr, int left,int right,int findValue) {
if (left > right) {
return new ArrayList<>();
}
int mid = (left + right) / 2;
int midValue = arr[mid];
if (findValue > midValue) {
return binSearch(arr,mid+1,right,findValue);
} else if(findValue < midValue){
return binSearch(arr,left,mid-1,findValue);
}else {
List<Integer> indexList = new ArrayList<>();
int temp = mid - 1;
while (true) {
if (temp < 0 || arr[temp] != findValue) {
break;
}
indexList.add(temp);
temp --;
}
indexList.add(mid);
temp = mid + 1;
while (true) {
if (temp > arr.length - 1 || arr[temp] != findValue) {
break;
}
indexList.add(temp);
temp ++;
}
return indexList;
}
}
}

Tags：

很赞哦！ ()

上一篇：基数排序法(图文)

下一篇：插值查找(图文)