二分查找的原理和用法

本篇內(nèi)容主要講解“二分查找的原理和用法”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學習“二分查找的原理和用法”吧!

概念

二分查找也稱折半查找（Binary Search），它是一種效率較高的查找方法。但是，折半查找要求線性表必須采用順序存儲結(jié)構(gòu)，而且表中元素按關鍵字有序排列

原理分析

前提

必須按照“大到小”或“小到大”的順序存儲的數(shù)組列表結(jié)構(gòu)

查找方法

• 列表進行折半, 取中間元素與目標值進行比較，判斷后決定舍去前半段或后半段，最終找到相等值

• 定義數(shù)組長度12，存儲1-12的整數(shù)，的查找過程示意圖

1. 找到值為3都索引

2. 找到值為13所在下標

3. 找到值為11所在下標

復雜度分析

實現(xiàn)方式

遞歸法

public int binarySearch(int[] arrays, int searchTag, int left, int right){
	int mid = (right + left) / 2;
	if (mid < 0 || mid >= arras.length){
		return -1;
	}
	if (arrays[mid] == searchTag){
		return mid;
	}
	if (arrays[mid] > searchTag){
		right = mid;
	} else if (arrays[mid] < searchTag){
		left = mid + 1;
	}
	if (left >= right){
		return -1;
	}
	return binarySearch(arrays, searchTag, left, right);
}

循環(huán)法

public int binarySearch(int[] arrays, int searchTag){
    int right = arrays.length, left = 0;
    while (left < right){
        int mod = (right + left) / 2;
        if (arrays[mid] == searchTag){
            return mid;
        } else if (arrays[mid] > searchTag){
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return -1;
}

到此，相信大家對“二分查找的原理和用法”有了更深的了解，不妨來實際操作一番吧！這里是億速云網(wǎng)站，更多相關內(nèi)容可以進入相關頻道進行查詢，關注我們，繼續(xù)學習！