欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数据结构与算法06 二分查找

程序员文章站 2022-07-08 13:21:46
...

二分法查找的思路如下:

  1. 首先,从数组的中间元素开始搜索,如果该元素正好是目标元素,则搜索过程结束,否则执行下一步。
  2. 如果目标元素大于/小于中间元素,则在数组大于/小于中间元素的那一半区域查找,然后重复第一步操作。
  3. 如果某一步数组为空,则表示不存在目标数。
    注:二分法查找只对有序数列有效。
    数据结构与算法06 二分查找

JAVA代码实现

代码可以解决当要查找的数在数组中可能存在多个的问题。当所查找的数不存在,则返回空列表。

public class BinarySearch {
    public static void main(String[] args) {
        int[] arr = new int[]{1,8,10,89,89,89,1000,1234};
        ArrayList<Integer> list = binarySearch(arr,0,arr.length-1,89);
        System.out.println(list);
    }

    public static ArrayList<Integer> binarySearch(int[] arr, int left, int right, int value){
        if (left > right){
            return new ArrayList();
        }

        int mid = (left + right) / 2;
        int midValue = arr[mid];

        if (value > midValue){
            return binarySearch(arr, mid + 1,right,value);
        }else if (value < midValue){
            return binarySearch(arr,left,mid-1,value);
        }else {
            ArrayList<Integer> list = new ArrayList<Integer>();
            list.add(mid);

            int temp = mid - 1;
            while (true){
                if (temp < left || arr[temp] != value){
                    break;
                }
                list.add(temp);
                temp -= 1;
            }

            temp = mid + 1;
            while (true){
                if (temp > right || arr[temp] != value){
                    break;
                }
                list.add(temp);
                temp += 1;
            }

            return list;
        }
    }
}
相关标签: 数据结构与算法