java实现二分法查找

内容摘要
什么是二分法查找:二分法也就是折半查找,在有序的数列中查找指定的元素,设定最小索引(low)和最大索引(height-1)还有中间值mid((low+height-1)/2),这种查找,如果中间值比指定元素小让lo
文章正文

什么是二分法查找:

二分法也就是折半查找,在有序的数列中查找指定的元素,设定最小索引(low)和最大索引(height-1)还有中间值mid((low+height-1)/2),这种查找,如果中间值比指定元素小让low=mid+1,如果中间值比指定元素大,让height=mid-1;

代码实现:(免费视频教程分享:java视频教程)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
  
public class Main2 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
                int arr[] = { 2, 5, 6, 8, 9, 4, 7 };
                Arrays.sort(arr);
                int deix(索引) = getxiabiao(arr, 7);
                 
            }
            public static int getxiabiao(int[] arr, int key) {
                int heigh = arr.length-1;
                int low = 0;
                int mid = 0;
                while (low <= heigh) {
                    mid = low + (heigh - low)/2;
                    if (arr[mid] == key) {
                        return mid;
                    } else if (arr[mid] < key) {
                        low = mid + 1;
                    } else if (arr[mid] > key) {
                        heigh = mid - 1;
                    }
                }
                return -1;
            }
        }

中间值的设定有两种方法;

算法一: mid = (low + high) / 2

算法二: mid = low + (high – low)/2

乍看起来,算法一简洁,算法二提取之后,跟算法一没有什么区别。但是实际上,区别是存在的。

算法一的做法,在极端情况下,(low + high)存在着溢出的风险,进而得到错误的mid结果,导致程序错误,而算法二能够保证计算出来的mid,一定大于low,小于high,不存在溢出的问题。

相关文章教程推荐:java入门教程

代码注释
[!--zhushi--]

作者:喵哥笔记

IDC笔记

学的不仅是技术,更是梦想!