二分查找---Java实现

略

Java代码实现，有递归和非递归的形式，并且对含有多个相同值的情况也做了处理，详见代码。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;


public class BinarySearch {
    private static int count = 0;

    public static void main(String[] args) {
        // 必须是有序的序列
        int[] array = {-1, 2, 4, 7, 9, 23, 53, 265, 265, 776};
        int[] sequence = new int[100];
        for (int i = 0; i < sequence.length; i++) {
            sequence[i] = i + 1;
        }

        System.out.println("生成的有序数组如下：");
        System.out.println(Arrays.toString(sequence));

        int result = binarySearch(sequence, 0, sequence.length - 1, 23);
        if (result == -1) {
            System.out.println("没有找到");
        } else {
            System.out.println("数组的下标位置是" + result);
        }

        ArrayList resultList = (ArrayList) binarySearchList(array, 0, array.length - 1, 265);
        System.out.println(resultList);
        if (resultList.size() == 0) {
            System.out.println("没有找到");
        } else {
            System.out.println("数组的下标位置是" + resultList);
        }
    }

    // 二分查找算法

    
    public static int binarySearch(int[] array, int left, int right, int findValue) {
        count++;
        System.out.println("查找次数~" + count);
        if (left > right) {
            return -1;
        }
        int mid = (left + right) / 2;
        if (array[mid] < findValue) {
            return binarySearch(array, mid + 1, right, findValue);
        } else if (array[mid] > findValue) {
            return binarySearch(array, left, mid - 1, findValue);
        } else {
            return mid;
        }
    }

    
    public static List binarySearchList(int[] array, int left, int right, int findValue) {
        if (left > right) {
            return new ArrayList<>();
        }
        int mid = (left + right) / 2;
        // 向 右递归
        if (array[mid] < findValue) {
            return binarySearchList(array, mid + 1, right, findValue);
            // 向左递归
        } else if (array[mid] > findValue) {
            return binarySearchList(array, left, mid - 1, findValue);
        } else {
            // 在有序的情况下，这个分支只会进来一次
            // 前提是在数组有序的情况下，所以找到一个值时，相同的值都在周围
            List resultIndexList = new ArrayList<>();

            //向mid 索引值的左边扫描，将所有满足的元素的下标，加入到集合ArrayList
            int temp = mid - 1;

            while (true) {
                if (temp < 0 || array[temp] != findValue) {
                    break;
                }
                resultIndexList.add(temp);
                //temp左移
                temp--;
            }

            // 在左边都遍历完的时候再加mid
            resultIndexList.add(mid);

            //向mid 索引值的右边扫描,将所有满足的元素的下标，加入到集合ArrayList
            temp = mid + 1;
            while (true) {
                if (temp > array.length - 1 || array[temp] != findValue) {
                    //退出
                    break;
                }
                //否则，就将temp 放入到 resultIndexList
                resultIndexList.add(temp);
                //temp右移
                temp++;
            }

            return resultIndexList;
        }
    }
}

import java.util.ArrayList;
import java.util.List;


public class BinarySearchNoRecursion {
    public static void main(String[] args) {
        //测试
        int[] arr = {1, 3, 8, 8, 8, 10, 11, 67, 100, 100, 100};
        int index = binarySearch(arr, 8);
        System.out.println("index=" + index);

        System.out.println("测试有多个相同值的情况");
        List res = binarySearchList(arr, 100);
        System.out.println(res);
    }

    
    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;
    }

    public static List binarySearchList(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;

        while (left <= right) {
            int mid = (left + right) / 2;
            if (arr[mid] == target) {
                List res = new ArrayList<>();
                int temp = mid - 1;
                while (true) {
                    if (temp < 0 || arr[temp] != target) {
                        break;
                    }
                    res.add(temp);
                    temp--;
                }
                res.add(mid);

                temp = mid + 1;
                while (true) {
                    if (temp > arr.length - 1 || arr[temp] != target) {
                        break;
                    }
                    res.add(temp);
                    temp++;
                }

                return res;
            } else if (arr[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }

        }
        return new ArrayList<>();
    }
}