二分查找实现及优化思考二分查找：实现：优化思考：

59 阅读 0 评论 39 点赞

我是靠谱客的博主火星上网络，最近开发中收集的这篇文章主要介绍二分查找实现及优化思考二分查找：实现：优化思考：，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

二分查找：

二分查找也叫折半查找，也就是把n个元素拆成一半一半查找。二分查找有两个要求第一个是要是有序的数列，第二个是必须存储在连续的存储结构中。假如数列是无序的，可以先使用排序算法排序。

实现：

分析：

1.定义个中间值middle，middle=（left+rigth)/2。把他做为要查找值的下标。
2.查找值key和middle比较：
key>middle说明查找值在middle的右边，改变left的值，left=middle+1.从而也改变了中间值。
key<middle查找值在middle的左边，改变rigth的值，rigth=middle-1.
key=middle时，输出下标middle。
注意我们何时结束查找呢
1.找到了查找值，结束。
2.left>rigth时结束（不是在循环中写left>rigth，这样会没有输出结果）

实现：

不递归的：

package day07;/*
Author:
date:
problem: 二分查找：（不递归）
    /*
    1.不递归的可以用while循环。middle=left+rigth/2
    2.left=0,ringth=array0.length用if判断是不是大于如果大于就把交换
     */


import java.util.Scanner;

public class binayarray {
    public static void main(String[] args) {
        int[] array0 = {1, 4, 6, 9, 10, 12, 14, 16, 18};
            int middle=0;//定义一个中间值，查找的下标
            int left = 0;
            int i=0;
            int rigth = array0.length - 1;
            System.out.println("请输入要查找的值");
            Scanner sca = new Scanner(System.in);
            int key = sca.nextInt();
            while (left<=rigth) {//当left>rigth时结束，说明已经循环完数组了
                middle = (left + rigth) / 2;
                if (key > array0[middle]) {
                    left = middle + 1;
                } else if (key < array0[middle]) {
                    rigth = middle - 1;
                } if (key == array0[middle]) {
                    i=middle;
                }
            }System.out.println(i);
        }
    }

优化思考：

1.数列有序，有重复值。
数列是升序排序，但数列中重复的值如{1，2，3，4，2，2，2，2，}我们查找2这个数时，只会输出第一重复值的下标
找到这个数的右边界，rigth–.

package day07;/*
Author:
date:
problem: 二分查找：（不递归）
    /*
    1.不递归的可以用while循环。middle=left+rigth/2
    2.left=0,ringth=array0.length用if判断是不是大于如果大于就把交换
     */


import java.util.Scanner;
//寻找边界值
public class binayarray {
    public static void main(String[] args) {
        int[] array0 = {1, 4, 6, 9, 9, 9, 14, 16, 18};
            int middle=0;//定义一个中间值，查找的下标
            int left = 0;
            int i=0;
            int rigth = array0.length - 1;
            System.out.println("请输入要查找的值");
            Scanner sca = new Scanner(System.in);
            int key = sca.nextInt();
            while (left<=rigth) {//当left>rigth时结束，说明已经循环完数组了
                middle = (left + rigth) / 2;
                if (key > array0[middle]) {
                    left = middle + 1;
                } else if (key < array0[middle]) {
                    rigth = middle - 1;
                } if (key == array0[middle]) {//有重复的数，可以收缩右边界，找到最边上的
                    rigth--;

                    i=middle;
                }
            }System.out.println(i);
        }
    }