二分查找法

红太狼 2022-09-14 09:58 169阅读 0赞

**算法描述**

** 折半的思想去定位要查找的元素**

**步骤:**

1.  前提：有已排序数组 A（假设已经做好）
2.  定义左边界 L、右边界 R，确定搜索范围，循环执行二分查找（3、4两步）
3.  获取中间索引 M = Floor((L+R) /2)
4.  中间索引的值 A\[M\] 与待搜索的值 T 进行比较
    
    ① A\[M\] == T 表示找到，返回中间索引
    
    ② A\[M\] > T，中间值右侧的其它元素都大于 T，无需比较，中间索引左边去找，M - 1 设置为右边界，重新查找
    
    ③ A\[M\] < T，中间值左侧的其它元素都小于 T，无需比较，中间索引右边去找， M + 1 设置为左边界，重新查找
5.  当 L > R 时，表示没有找到，应结束循环

package com.xxl.job.admin;
    
    public class BinarySearch {
        public static void main(String[] args) {
            int[] array = {1, 5, 8, 11, 19, 22, 31, 35, 40, 45, 48, 49, 50};
            int target = 48;
            int idx = binarySearch(array, target);
            System.out.println(idx);
    
    
        }
    
    	// 二分查找, 找到返回元素索引，找不到返回 -1
    	public static int binarySearch(int[] a, int t) {
        	int l = 0 ,r = a.length-1;
    		while (l <= r) {
    //			int m = (l +r ) /2;   integer.max_value ; 精度溢出
    			int m = (l +r ) >>>1;  // cpu 执行位于效率高
    			if (a[m] == t){
    				return m;
    			}else if (a[m]< t){
    				l = m+1;
    			}else{
    				r = m - 1;
    			}
    		}
    
        	return -1;
    	}
    	
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，169人围观）

还没有评论，来说两句吧...

相关阅读

相关二分查找法

前提是在已经排好序的数组中，通过将待查找的元素与中间的索引值对应的元素进行比较，若大于中间索引值对应的元素，去右半部分查找，否则，去左半部分查找。以此类推，直到找到为止；找不到

野性酷女/ 2024年01月01日 06:49/ 0 赞/ 282 阅读

相关二分查找法

理解二分查找二分查找，在一组有序数中查找你想要的找到的数值。比如在数组arr\[10\] = \{1,2,3,4,5,6,7,8,9,10\}，中查找一个数字7。

电玩女神/ 2023年10月08日 14:16/ 0 赞/ 14 阅读

相关二分查找法

想使用二分查找法，前提是这个数列需要是有序的 template<typename T> int binarySearch(T arr[],int n, T t

柔光的暖阳◎/ 2022年10月21日 03:49/ 0 赞/ 133 阅读

相关二分查找法

算法描述折半的思想去定位要查找的元素步骤: 1. 前提：有已排序数组 A（假设已经做好） 2. 定义左边界 L、右边界 R，确定搜索范围，循环执行二分查找（3、

红太狼/ 2022年09月14日 09:58/ 0 赞/ 170 阅读

相关二分查找法分析

二分查找针对的是一个有序的数组其思想还是比较简单的，我们假设这个有序数组的顺序是从小到大排序的，我们拿一个目标值与数组最中间的一个值进行比较，两个数进行比较有三种情况：

刺骨的言语ヽ痛彻心扉/ 2022年08月23日 03:47/ 0 赞/ 186 阅读

相关 java 二分查找法

数组sort排序后通过二分查找得到的索引位置已经不是初始数组的位置了，所以它真正“实用” 在哪里呢？下面例子中99排序前是在索引位置5，排序后却是6，所以结果不

不念不忘少年蓝@/ 2022年08月17日 15:19/ 0 赞/ 159 阅读

相关 1、二分查找法

二分查找算法 1.二分查找又称折半查找，它是一种效率较高的查找方法。 2.二分查找要求：（1）必须采用顺序存储结构（2）必须按关键字大小有序排列 3.原理：将数组

蔚落/ 2022年05月27日 03:29/ 0 赞/ 153 阅读

相关二分查找法

二分查找法，所需查找次数最高为logn,以2为底 def binary_search(list, item): low and high keep tr

心已赠人/ 2022年05月18日 00:41/ 0 赞/ 175 阅读

相关二分查找法

最基本的二分查找法、不考虑数组有重复数据、匹配到返回具体元素、没有返回-1 public class TestBinary { public int

淡淡的烟草味﹌/ 2022年02月27日 09:24/ 0 赞/ 253 阅读

相关 [查找算法]二分查找法

二分查找法是经典的入门算法,以高效和广泛应用而著称. 算法是由静态方法rank() 实现的，它接受一个整数键和一个已经有序的int 数组作为参数。如果该键存在于数组中

「爱情、让人受尽委屈。」/ 2022年02月22日 02:49/ 0 赞/ 241 阅读