Shulou(Shulou.com)06/03 Report--

This article introduces the relevant knowledge of "how to use dichotomy to find". In the operation of actual cases, many people will encounter such a dilemma. Then let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

1. The background of dichotomy search

When the number of elements stored in an array or collection is very large, if you want to track the location or existence of a specific element, the conventional way is to loop through each element until you find the element you are looking for. This kind of search method is very inefficient, so we need to use dichotomy to improve the search efficiency.

2. Introduction of dichotomy search

Dichotomy search (half search) to find the location of the specified value

Baidu encyclopedia introduces the dichotomy search as follows:

3. The algorithm idea of dichotomy search.

Suppose the array is sorted in ascending order. For a given target value, aim, start at the middle of the array: 1. If the lookup data is exactly equal to the intermediate element value, the index of the intermediate element value is returned; 2. If the search value is smaller than the middle value, the first half of the whole search range is taken as the new search area; 3. If the search value is larger than the middle value, the second half of the whole search range is taken as the new search area. Note: if the search succeeds, the index is returned, and the failure returns-1.

4. Code implementation

4.1 using loop to realize dichotomy search

Public class BinarySearch {public static void main (String [] args) {/ / generate a random array int [] array = suiji (); / / sort a pair of random arrays Arrays.sort (array); System.out.println ("the random array generated is:" + Arrays.toString (array)); System.out.println ("value to look up:") Scanner input = new Scanner (System.in); / / the target value for the search int aim = input.nextInt (); / / use dichotomy to find int index = binarySearch (array, aim); System.out.println ("Index position of the found value:" + index) } / * generate a random array * * @ return returns a random array * / private static int [] suiji () {/ / random.nextInt (n) + m returns the random number int n = new Random () .nextInt (6) + 5 from m to m+n-1; int [] array = new int [n] / / Loop iterates to assign for (int I = 0; I) to the array

< array.length; i++) { array[i] = new Random().nextInt(100); } return array; } /** * 二分法查找 ---循环的方式实现 * * @param array 要查找的数组 * @param aim 要查找的值 * @return 返回值，成功返回索引，失败返回-1 */ private static int binarySearch(int[] array, int aim) { // 数组最小索引值 int left = 0; // 数组最大索引值 int right = array.length - 1; int mid; while (left array[mid]) { left = mid + 1; // 若查找数据与中间元素值正好相等，则放回中间元素值的索引 } else { return mid; } } return -1; } } 代码执行结果： 产生的随机数组为： [16, 33, 40, 46, 57, 63, 65, 71, 85] 要进行查找的值： 46 查找的值的索引位置： 3 若输入的值找不到，则返回-1 产生的随机数组为： [28, 41, 47, 56, 70, 81, 85, 88, 95] 要进行查找的值： 66 查找的值的索引位置： -1 4.2 利用递归的方式实现二分法查找 public class BinarySearch3 { public static void main(String[] args) { // 生成一个随机数组 int[] array = suiji(); // 对随机数组排序 Arrays.sort(array); System.out.println("产生的随机数组为： " + Arrays.toString(array)); System.out.println("要进行查找的值： "); Scanner input = new Scanner(System.in); // 进行查找的目标值 int aim = input.nextInt(); // 使用二分法查找 int index = binarySearch(array, aim, 0, array.length - 1); System.out.println("查找的值的索引位置： " + index); } /** * 生成一个随机数组 * * @return 返回值，返回一个随机数组 */ private static int[] suiji() { // Random.nextInt(n)+m 返回m到m+n-1之间的随机数 int n = new Random().nextInt(6) + 5; int[] array = new int[n]; // 循环遍历为数组赋值 for (int i = 0; i < array.length; i++) { array[i] = new Random().nextInt(100); } return array; } /** * 二分法查找 ---递归的方式 * * @param array 要查找的数组 * @param aim 要查找的值 * @param left 左边最小值 * @param right 右边最大值 * @return 返回值，成功返回索引，失败返回-1 */ private static int binarySearch(int[] array, int aim, int left, int right) { if (aim < array[left] || aim >

Array [right]) {return-1;} / / find the intermediate value int mid = (left + right) / 2; if (array [mid] = = aim) {return mid } else if (array [mid] > aim) {/ / if the intermediate value is greater than the value you are looking for, continue recursive return binarySearch (array, aim, left, mid-1) from the left half;} else {/ / if the intermediate value is less than the value you are looking for, continue recursive return binarySearch from the right half (array, aim, mid + 1, array.length-1) }

Compared with the loop, the recursion code is more concise, but the time and space consumption is relatively large, and the efficiency is low. In the actual study and work, choose to use it according to the situation.

This is the end of "how to use dichotomy to find". Thank you for your reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.