前提
必須是有序數(shù)組夺溢。
思路
image.png
無(wú)重復(fù)數(shù)組二分查找
package com.pl.arithmetic.search;
import java.util.ArrayList;
import java.util.List;
/**
* <p>
*
* @Description: TODO
* </p>
* @ClassName BinarySearch
* @Author pl
* @Date 2020/12/20
* @Version V1.0.0
*/
public class BinarySearch {
public static void main(String[] args) {
int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 , 11, 12, 13,14,15,16,17,18,19,20 };
int resIndex = binarySearch(arr, 0, arr.length - 1, 11);
System.out.println("resIndex=" + resIndex);
}
public static int binarySearch(int[] arr,int leftIndex,int rightIndex,int targetValue){
//todo 先判斷是否需要查找
if (leftIndex>rightIndex){
return -1;
}
//todo 中指比較,遞歸查找
int midIndex = (leftIndex+rightIndex)/2;
int midValue = arr[midIndex];
if (midValue == targetValue){
return midIndex;
}
//和midValue比較杂拨，如果小于midValue，左遞歸枕磁，反之右遞歸
if (midValue>targetValue){
return binarySearch(arr,0, midIndex-1,targetValue);
}else {
return binarySearch(arr,midIndex+1,rightIndex,targetValue);
}
}
}
有重復(fù)數(shù)組二分查找
思路
1.退出條件
leftIndx>rightIndex
2.中值比較
如果相等许起，先不退出，因?yàn)榍疤崾怯行驍?shù)組蚂会，找其左右是否也有相同值，直到左右都不等于targetValue
3.二分遞歸
package com.pl.arithmetic.search;
import java.util.ArrayList;
import java.util.List;
/**
* <p>
*
* @Description: TODO
* </p>
* @ClassName BinarySearch
* @Author pl
* @Date 2020/12/20
* @Version V1.0.0
*/
public class BinarySearch {
public static void main(String[] args) {
int arr[] = { 1, 8, 10, 89,1000,1000,1000, 1234 };
// int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 , 11, 12, 13,14,15,16,17,18,19,20 };
//
/* int resIndex = binarySearch(arr, 0, arr.length - 1, 11);
System.out.println("resIndex=" + resIndex);*/
List<Integer> resIndexList = binarySearchPlus(arr, 0, arr.length - 1, 1000);
System.out.println("resIndexList=" + resIndexList);
}
public static int binarySearch(int[] arr,int leftIndex,int rightIndex,int targetValue){
//todo 先判斷是否需要查找
if (leftIndex>rightIndex){
return -1;
}
//todo 中指比較,遞歸查找
int midIndex = (leftIndex+rightIndex)/2;
int midValue = arr[midIndex];
if (midValue == targetValue){
return midIndex;
}
//和midValue比較耗式，如果小于midValue胁住，左遞歸，反之右遞歸
if (midValue>targetValue){
return binarySearch(arr,0, midIndex-1,targetValue);
}else {
return binarySearch(arr,midIndex+1,rightIndex,targetValue);
}
}
//完成一個(gè)課后思考題:
/*
* 課后思考題： {1,8, 10, 89, 1000, 1000刊咳，1234} 當(dāng)一個(gè)有序數(shù)組中彪见，
* 有多個(gè)相同的數(shù)值時(shí)，如何將所有的數(shù)值都查找到娱挨，比如這里的 1000
*
* 思路分析
* 1. 在找到mid 索引值余指，不要馬上返回
* 2. 向mid 索引值的左邊掃描，將所有滿(mǎn)足 1000跷坝， 的元素的下標(biāo)酵镜，加入到集合ArrayList
* 3. 向mid 索引值的右邊掃描，將所有滿(mǎn)足 1000探孝， 的元素的下標(biāo)笋婿，加入到集合ArrayList
* 4. 將Arraylist返回
*/
public static List<Integer> binarySearchPlus(int[] arr, int leftIndex, int rightIndex, int targetValue){
//todo 先判斷是否需要查找
//只有遍歷了整個(gè)數(shù)組都沒(méi)找到所要的targetValue才會(huì)到滿(mǎn)足這個(gè)條件
if (leftIndex>rightIndex){
return new ArrayList<Integer>();
}
//todo 遞歸查找誉裆，中指比較,找到后不立即退出顿颅，因?yàn)槎植檎仪疤崾怯行驍?shù)組，需要查找其值左右是否為要找的項(xiàng)足丢，左右兩邊查找粱腻，直到其左右兩邊都不等于targetValue庇配，返回targetIndexList
int midIndex = (leftIndex+rightIndex)/2;
int midValue = arr[midIndex];
if (midValue == targetValue){
List<Integer> targetIndexList = new ArrayList<>();
targetIndexList.add(midIndex);
//從midIndex左面線(xiàn)性查找
int midLeftIndex = midIndex -1;
while (true){
if (midLeftIndex<leftIndex || arr[midLeftIndex]!=targetValue){
break;
}
targetIndexList.add(midLeftIndex);
midLeftIndex--;
}
//從midIndex右面查找
int midRightIndex = midIndex+1;
while (true){
if (midRightIndex>rightIndex || arr[midRightIndex] != targetValue){
break;
}
targetIndexList.add(midRightIndex);
midRightIndex++;
}
return targetIndexList;
}
//和midValue比較，如果小于midValue绍些，左遞歸捞慌，反之右遞歸
if (midValue>targetValue){
return binarySearchPlus(arr,0, midIndex-1,targetValue);
}else {
return binarySearchPlus(arr,midIndex+1,rightIndex,targetValue);
}
}
}
錯(cuò)誤code
package com.pl.arithmetic.search;
import java.util.ArrayList;
import java.util.List;
/**
* <p>
*
* @Description: TODO
* </p>
* @ClassName BinarySearch
* @Author pl
* @Date 2020/12/20
* @Version V1.0.0
*/
public class BinarySearch {
public static void main(String[] args) {
int arr[] = { 1, 8, 10, 89,1000,1000, 1234 };
// int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 , 11, 12, 13,14,15,16,17,18,19,20 };
//
/* int resIndex = binarySearch(arr, 0, arr.length - 1, 11);
System.out.println("resIndex=" + resIndex);*/
List<Integer> resIndexList = binarySearchPlus(arr, 0, arr.length - 1, 1000);
System.out.println("resIndexList=" + resIndexList);
}
public static int binarySearch(int[] arr,int leftIndex,int rightIndex,int targetValue){
//todo 先判斷是否需要查找
if (leftIndex>rightIndex){
return -1;
}
//todo 中指比較,遞歸查找
int midIndex = (leftIndex+rightIndex)/2;
int midValue = arr[midIndex];
if (midValue == targetValue){
return midIndex;
}
//和midValue比較，如果小于midValue柬批，左遞歸啸澡，反之右遞歸
if (midValue>targetValue){
return binarySearch(arr,0, midIndex-1,targetValue);
}else {
return binarySearch(arr,midIndex+1,rightIndex,targetValue);
}
}
//完成一個(gè)課后思考題:
/*
* 課后思考題： {1,8, 10, 89, 1000, 1000，1234} 當(dāng)一個(gè)有序數(shù)組中氮帐，
* 有多個(gè)相同的數(shù)值時(shí)嗅虏，如何將所有的數(shù)值都查找到，比如這里的 1000
*
* 思路分析
* 1. 在找到mid 索引值上沐，不要馬上返回
* 2. 向mid 索引值的左邊掃描皮服，將所有滿(mǎn)足 1000， 的元素的下標(biāo)参咙，加入到集合ArrayList
* 3. 向mid 索引值的右邊掃描龄广，將所有滿(mǎn)足 1000， 的元素的下標(biāo)蕴侧，加入到集合ArrayList
* 4. 將Arraylist返回
*/
public static List<Integer> binarySearchPlus(int[] arr, int leftIndex, int rightIndex, int targetValue){
//todo 先判斷是否需要查找
//只有遍歷了整個(gè)數(shù)組都沒(méi)找到所要的targetValue才會(huì)到滿(mǎn)足這個(gè)條件
if (leftIndex>rightIndex){
return new ArrayList<Integer>();
}
//todo 遞歸查找择同，中指比較,找到后不立即退出，因?yàn)槎植檎仪疤崾怯行驍?shù)組净宵，需要查找其值左右是否為要找的項(xiàng)奠衔，左右兩邊查找，直到其左右兩邊都不等于targetValue塘娶，返回targetIndexList
int midIndex = (leftIndex+rightIndex)/2;
int midValue = arr[midIndex];
if (midValue == targetValue){
List<Integer> targetIndexList = new ArrayList<>();
targetIndexList.add(midIndex);
//從midIndex左面線(xiàn)性查找
int midLeftIndex = --midIndex;
while (true){
if (midLeftIndex<leftIndex || arr[midLeftIndex]!=targetValue){
break;
}
targetIndexList.add(midLeftIndex);
midLeftIndex--;
}
//從midIndex右面查找
int midRightIndex = ++midIndex;
while (true){
if (midRightIndex>rightIndex || arr[midRightIndex] != targetValue){
break;
}
targetIndexList.add(midRightIndex);
midRightIndex++;
}
return targetIndexList;
}
//和midValue比較归斤，如果小于midValue，左遞歸刁岸，反之右遞歸
if (midValue>targetValue){
return binarySearchPlus(arr,0, midIndex-1,targetValue);
}else {
return binarySearchPlus(arr,midIndex+1,rightIndex,targetValue);
}
}
}
輸出[5,4,5]
analyze
73,82行出錯(cuò)
int midLeftIndex = --midIndex;
int midRightIndex = ++midIndex;
這樣賦值脏里，midIndex內(nèi)存地質(zhì)發(fā)生變化
