当前位置:首页 » 《随便一记》 » 正文

【程序员必会十大算法】之二分查找算法_Android小白

13 人参与  2022年01月12日 10:52  分类 : 《随便一记》  评论

点击全文阅读


1.递归实现

①不考虑相同数
/**
 * 二分查找,不考虑有相同数的情况(递归)
 * @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;
        }
    }
}

2.非递归实现

①不考虑有相同数
/**
 * 二分查找,不考虑有相同数的情况(非递归)
 * @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;
            }
        }
    }
}

点击全文阅读


本文链接:http://zhangshiyu.com/post/33084.html

递归  查找  情况  
<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

最新文章

  • 全书浏览重生后联姻丈夫爱上KTV小妹,我死遁了(姜满裴聿琛温舒柠)_重生后联姻丈夫爱上KTV小妹,我死遁了(姜满裴聿琛温舒柠)全书结局
  • 时筠荣景琛小说(荣少的步步沦陷)外篇+结局(时筠荣景琛)全篇在线阅读
  • 重生在高考前,我笑着送小青梅和小混混去庆祝成人礼老书虫(沈晏安乔念),重生在高考前,我笑着送小青梅和小混混去庆祝成人礼老书虫
  • 送子观音优质(殷茵程沐白)全书免费_(殷茵程沐白)送子观音优质后续(殷茵程沐白)
  • 重生后,我笑送全班去三亚毕业旅行推荐_徐凯沈清别以为阅读_小说后续在线阅读_无删减免费完结_
  • 北风秋霜覆往忆完结+结局+番外(傅砚寒沈沐柒)全书浏览_北风秋霜覆往忆完结+结局+番外全书浏览
  • 小说大结局小说罗毅小说已更新+特别篇(转职神级辅助,转身上报国家!)纯净版
  • 碎骨揉香与君长诀精修版(褚明意萧鹤明)全书浏览_碎骨揉香与君长诀精修版全书浏览
  • 只因一块表,闺蜜害死我全家热门榜首_陆哲轩李俏陆少爆火全网_小说后续在线阅读_无删减免费完结_
  • 折寒枝簪起霜思全章+后续+结局(宋闻璟沈棠眠)_折寒枝簪起霜思全章+后续+结局(宋闻璟沈棠眠)
  • 高考前一周我绑定了上分系统(袁文淼徐靓靓)_高考前一周我绑定了上分系统(袁文淼徐靓靓)
  • 元乐曦楚寻风:结局+番外免费品鉴终极反转(楚寻风元乐曦):结局+番外评价五颗星

    关于我们 | 我要投稿 | 免责申明

    Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1