java算法-二分法查找实现

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

flowchart 箭头图标勿删

什么是二分法查找

首先，使用二分法查找的前提是：被查找的数组已排好序

具体实现：

假如有一组数为3，12，24，36，55，68，75，88要查给定的值24.可设三个变量front，mid，end分别指向数据的上界，中间和下界，mid=（front+end）/2.

1.开始令front=0（指向3），end=7（指向88），则mid=3（指向36）。因为a[mid]>x，故应在前半段中查找。

2.令新的end=mid-1=2，而front=0不变，则新的mid=1。此时x>a[mid]，故确定应在后半段中查找。

3.令新的front=mid+1=2，而end=2不变，则新的mid=2，此时a[mid]=x，查找成功，返回查找元素的索引。

如果要查找的数不是数列中的数，例如x=25，当第三次判断时，x>a[mid]，按以上规律，令front=mid+1，即front=3，出现front>end的情况，表示查找不成功，放回-1。

二分法查找使用场景

二分法查找适用于数据量较大时，但是数据需要先排好顺序。对于我们很多人来说，还是用于面试……

代码实现

package com.xzlf.binarySearch;

import java.util.Arrays;

public class TestBinarySearch {

	public static void main(String[] args) {

		int[ ] arr = { 30,20,50,10,80,9,7,12,100,40,8};

		int searchWord = 20; // 所要查找的数

		Arrays.sort(arr); //二分法查找之前，一定要对数组元素排序

		System.out.println(Arrays.toString(arr));

		System.out.println(searchWord+"元素的索引："+binarySearch(arr,searchWord));

		System.out.println("========================");

		int errorWord = 66; // 查找不存在的数

		System.out.println(errorWord+"元素的索引："+binarySearch(arr,errorWord));

	}

	public static int binarySearch(int[] arr, int value) {

		int low = 0; // 开始位置

		int high = arr.length - 1; // 结束 位置

		while(low <= high) {

			int middle = (low + high) / 2;

			if (value == arr[middle]) {

				return middle; //返回查询到的索引位置

			}

			if (value > arr[middle]) {

				low = middle + 1;

			}

			if (value < arr[middle]) {

				high = middle - 1;

			}

		}

		//上面循环完毕，说明未找到，返回-1

		return -1;

	}

}