脚本宝典收集整理的这篇文章主要介绍了【程序员必会十大算法】之二分查找算法，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。
/**
* 二分查找，不考虑有相同数的情况（递归）
* @param arr
* @param left
* @param right
* @param findVal
* @return
*/
public static int binarySeArch(int[] arr,int left,int right,int findVal){
if (left > right || arr[0] > findVal || arr[arr.length - 1] < findVal){
return -1;
}else {
int mid = (left + right) / 2;
if (arr[mid] > findVal){
return binarySearch(arr,left,mid - 1,findVal);
}else if (arr[mid] < findVal){
return binarySearch(arr,mid + 1,right,findVal);
}else {
//找到了
return mid;
}
}
}
/**
* 二分查找 考虑有相同元素的情况（递归）
* @param arr
* @param left
* @param right
* @param findVal 要查找的值
* @return
*/
public static ArrayList<Integer> binarySearch1(int[] arr,int left,int right,int findVal){
if (left > right || arr[0] > findVal || arr[arr.length - 1] < findVal){
return null;
}else {
int mid = (left + right) / 2;
if (arr[mid] > findVal){
return binarySearch1(arr,left,mid - 1,findVal);
}else if (arr[mid] < findVal){
return binarySearch1(arr,mid + 1,right,findVal);
}else {
ArrayList<Integer> arrayList = new ArrayList<>();
//先往左走
int midleft = mid - 1;
while (midLeft >= 0 && arr[midLeft] == findVal){
arrayList.add(midLeft);
midLeft--;
}
Collections.reverse(arrayList);
arrayList.add(mid);
int midRight = mid + 1;
while (midRight < arr.length && arr[midRight] == findVal){
arrayList.add(midRight);
midRight++;
}
return arrayList;
}
}
}
/**
* 二分查找，不考虑有相同数的情况（非递归）
* @param arr
* @param findVal
* @return
*/
public static int binarySearch3(int[] arr,int findVal){
int left = 0;
int right = arr.length - 1;
while (left <= right){
int mid = (left + right) / 2;
if (arr[mid] > findVal){
right = mid - 1;
}else if (arr[mid] < findVal){
left = mid + 1;
}else {
return mid;
}
}
return -1;
}
/**
* 二分查找，考虑有相同数的情况（非递归）
* @param arr
* @param findVal
* @return
*/
public static ArrayList<Integer> binarySearch4(int[] arr,int findVal){
int left = 0;
int right = arr.length - 1;
while (left <= right){
int mid = (left + right) / 2;
if (arr[mid] > findVal){
right = mid - 1;
}else if (arr[mid] < findVal){
left = mid + 1;
}else {
ArrayList<Integer> arrayList = new ArrayList<>();
int midLeft = mid - 1;
while (midLeft > 0 && arr[midLeft] == findVal){
arrayList.add(midLeft);
midLeft--;
}
Collections.reverse(arrayList);
arrayList.add(mid);
int midRight = mid + 1;
while (midRight < arr.length && arr[midRight] == findVal){
arrayList.add(midRight);
midRight++;
}
return arrayList;
}
}
return new ArrayList<>();
}
public class Main {
public static void main(String[] args) {
int[] arr = {1,1,2,2,33};
}
/**
* 二分查找，考虑有相同数的情况（非递归）
* @param arr
* @param findVal
* @return
*/
public static ArrayList<Integer> binarySearch4(int[] arr,int findVal){
int left = 0;
int right = arr.length - 1;
while (left <= right){
int mid = (left + right) / 2;
if (arr[mid] > findVal){
right = mid - 1;
}else if (arr[mid] < findVal){
left = mid + 1;
}else {
ArrayList<Integer> arrayList = new ArrayList<>();
int midLeft = mid - 1;
while (midLeft > 0 && arr[midLeft] == findVal){
arrayList.add(midLeft);
midLeft--;
}
Collections.reverse(arrayList);
arrayList.add(mid);
int midRight = mid + 1;
while (midRight < arr.length && arr[midRight] == findVal){
arrayList.add(midRight);
midRight++;
}
return arrayList;
}
}
return new ArrayList<>();
}
/**
* 二分查找，不考虑有相同数的情况（非递归）
* @param arr
* @param findVal
* @return
*/
public static int binarySearch3(int[] arr,int findVal){
int left = 0;
int right = arr.length - 1;
while (left <= right){
int mid = (left + right) / 2;
if (arr[mid] > findVal){
right = mid - 1;
}else if (arr[mid] < findVal){
left = mid + 1;
}else {
return mid;
}
}
return -1;
}
/**
* 二分查找 考虑有相同元素的情况（递归）
* @param arr
* @param left
* @param right
* @param findVal 要查找的值
* @return
*/
public static ArrayList<Integer> binarySearch1(int[] arr,int left,int right,int findVal){
if (left > right || arr[0] > findVal || arr[arr.length - 1] < findVal){
return null;
}else {
int mid = (left + right) / 2;
if (arr[mid] > findVal){
return binarySearch1(arr,left,mid - 1,findVal);
}else if (arr[mid] < findVal){
return binarySearch1(arr,mid + 1,right,findVal);
}else {
ArrayList<Integer> arrayList = new ArrayList<>();
//先往左走
int midLeft = mid - 1;
while (midLeft >= 0 && arr[midLeft] == findVal){
arrayList.add(midLeft);
midLeft--;
}
Collections.reverse(arrayList);
arrayList.add(mid);
int midRight = mid + 1;
while (midRight < arr.length && arr[midRight] == findVal){
arrayList.add(midRight);
midRight++;
}
return arrayList;
}
}
}
/**
* 二分查找，不考虑有相同数的情况（递归）
* @param arr
* @param left
* @param right
* @param findVal
* @return
*/
public static int binarySearch(int[] arr,int left,int right,int findVal){
if (left > right || arr[0] > findVal || arr[arr.length - 1] < findVal){
return -1;
}else {
int mid = (left + right) / 2;
if (arr[mid] > findVal){
return binarySearch(arr,left,mid - 1,findVal);
}else if (arr[mid] < findVal){
return binarySearch(arr,mid + 1,right,findVal);
}else {
//找到了
return mid;
}
}
}
}
以上是脚本宝典为你收集整理的【程序员必会十大算法】之二分查找算法全部内容，希望文章能够帮你解决【程序员必会十大算法】之二分查找算法所遇到的问题。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。