二分查找法

红太狼 2022-09-14 09:58 286阅读 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 条评论，286人围观）

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

相关阅读

相关二分查找法

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

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

相关二分查找法

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

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

相关二分查找法

概述：二分查找法又称折半查找法，是一种效率较高的查找方式，但，二分查找法要求数组必须采用顺序存储结构有序排列。下面是相关代码： public class Demo

你的名字/ 2023年10月03日 11:19/ 0 赞/ 29 阅读

相关二分查找法（折半查找法）

要求：给定数组必须要是有序的（要么从小到大，要么从大到小排序）。 -------------------- 原理:二分法查找（Binary Search）也称折半查找

╰半夏微凉°/ 2023年06月15日 11:01/ 0 赞/ 128 阅读

相关二分查找法

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

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

相关二分查找法

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

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

相关二分查找法

package com.wdl.day07; / @创建人 wdl @创建时间 2021/8/9 @描述 / public class

小鱼儿/ 2022年09月04日 01:45/ 0 赞/ 125 阅读

相关二分查找法

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

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

相关二分查找法

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

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

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

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

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