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

This article will explain in detail how to use java to achieve binary search. The editor thinks it is very practical, so I share it for you as a reference. I hope you can get something after reading this article.

1. The idea of binary search algorithm

The ordered sequence is compared with the keywords to be searched by the number of positions in the middle of the sequence, narrowing the search range by half each time until the match is successful.

A scenario: compare the keyword recorded in the middle of the table with the lookup keyword, and if the two are equal, the search is successful; otherwise, the table is divided into the first and last two sub-tables by using the intermediate location record. if the keyword of the intermediate location record is greater than the lookup keyword, then further look for the previous subtable, otherwise further look for the latter subtable. Repeat the above process until a record that meets the criteria is found, making the search successful, or until the child table does not exist, where the lookup is not successful.

2. Dichotomy search icon description

Pictures from Baidu Pictures:

3. Advantages and disadvantages of binary search.

Advantages:

Less comparison times, fast search speed and good average performance

Disadvantages:

It is required that the table to be checked is an ordered table, and it is difficult to insert and delete.

Therefore, the half-and-half search method is suitable for searching ordered lists that change infrequently.

Conditions of use:

The search sequence is sequentially structured and ordered.

3. Java code implementation 3.1 uses recursive implementation

/ * * use recursive binary search * title:recursionBinarySearch * @ param arr ordered array * @ param key to find the keyword * @ return found location * / public static int recursionBinarySearch (int [] arr,int key,int low,int high) {if (key)

< arr[low] || key >

Arr [high] | | low > high) {return-1;} int middle = (low + high) / 2; / / initial intermediate position if (arr > key) {/ / the keyword is larger than the keyword in the left region return recursionBinarySearch (arr, key, low, middle-1);} else if (arr [middle])

< key){ //比关键字小则关键字在右区域 return recursionBinarySearch(arr, key, middle + 1, high); }else { return middle; } }3.1 不使用递归实现（while循环） /** * 不使用递归的二分查找 *title:commonBinarySearch *@param arr *@param key *@return 关键字位置 */ public static int commonBinarySearch(int[] arr,int key){ int low = 0; int high = arr.length - 1; int middle = 0; //定义middle if(key < arr[low] || key >

Arr [high] | | low > high) {return-1;} while (low key) {/ / larger than the keyword, the keyword is in the left region high = middle-1;} else if (arr [middle]

< key){ //比关键字小则关键字在右区域 low = middle + 1; }else{ return middle; } } return -1; //最后仍然没有找到，则返回-1 }3.3 测试 测试代码： public static void main(String[] args) { int[] arr = {1,3,5,7,9,11}; int key = 4; //int position = recursionBinarySearch(arr,key,0,arr.length - 1); int position = commonBinarySearch(arr, key); if(position == -1){ System.out.println("查找的是"+key+",序列中没有该数！"); }else{ System.out.println("查找的是"+key+",找到位置为："+position); } } recursionBinarySearch()的测试：key分别为0，9，10，15的查找结果 查找的是0,序列中没有该数！ 查找的是9,找到位置为：4 查找的是10,序列中没有该数！ 查找的是15,序列中没有该数！ commonBinarySearch()的测试：key分别为-1，5，6，20的查找结果 查找的是-1,序列中没有该数！ 查找的是5,找到位置为：2 查找的是6,序列中没有该数！ 查找的是20,序列中没有该数！ 4、时间复杂度 采用的是分治策略 最坏的情况下两种方式时间复杂度一样：O(log2 N)

Best case is O (1)

5. Space complexity

The space complexity of the algorithm is not to calculate the actual space occupied, but to calculate the number of auxiliary space units of the whole algorithm.

Non-recursive method:

Because the auxiliary space is constant, so: the space complexity is O (1).

Recursive method: the number and depth of recursion are both log2 N, and the auxiliary space required each time is constant:

Space complexity: O (log2N)

On "how to use java to achieve binary search" this article is shared here, I hope the above content can be of some help to you, so that you can learn more knowledge, if you think the article is good, please share it out for more people to see.

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.