Java implements binary search

What is binary search:

Biometric search is also a binary search. It searches for the specified element in an ordered sequence and sets the minimum index (low) and The maximum index (height-1) and the middle value mid ((low height-1)/2). For this search, if the middle value is smaller than the specified element, let low=mid 1. If the middle value is larger than the specified element, let height =mid-1;

Code implementation: (Free video tutorial sharing: java video tutorial)

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;
			}
		}

There are two ways to set the intermediate value;

Algorithm one: mid = (low high) / 2

Algorithm two: mid = low (high – low)/2

At first glance, algorithm one is simple, and algorithm two extracts After that, there is no difference from Algorithm 1. But in fact, the difference exists.

The approach of Algorithm 1, in extreme cases, there is a risk of overflow (low high), which will lead to wrong mid results, leading to program errors, while Algorithm 2 can ensure that the calculated mid must be greater than low , less than high, there is no overflow problem.

Recommended related articles and tutorials: java introductory tutorial

The above is the detailed content of Java implements binary search. For more information, please follow other related articles on the PHP Chinese website!