Briefly describe the binary search algorithm and time complexity, and implement a binary search algorithm

[[432404]]

Binary search is also called half-search algorithm. It is a simple and easy-to-understand fast search algorithm. For example, I randomly write a number between 0-100 and ask you to guess what I wrote. Every time you guess, I will tell you whether your guess is too high or too low, until you guess it right.

This algorithm requires that the array to be searched has been sorted, and the implementation steps are as follows:

• Select the middle number in an array
• The search number is compared with the middle number. If it is lower than the middle number, search in the subarray to the left of the middle number; if it is higher than the middle number, search in the subarray to the right of the middle number; if they are equal, return a successful search.
• Repeat the previous step until the search succeeds or fails.

 function binarySearch(items, item) {
 var low = 0,
        high = items.length - 1,
 mid, elem
 while(low <= high) {
        mid = Math.floor((low+high)/2)
 elem = items[mid]
 if(elem < item) {
 low = mid + 1
        } else if(elem > item) {
 high = mid - 1
 } else {
 return mid
 }
 }
 return -1
 } 
 
 // test
 var arr = [2,3,1,4]
 // Quick sort
 quickSort(arr) 
 
 binarySearch(arr, 3)
 // 2 
 
 binarySearch(arr, 5)
 // -1

Test success

Binary search error-prone points:

• The loop exit condition is low <= high. Note that it is <=
• The value of mid is Math.floor((low+high)/2)
• low high Each time it is updated, low = mid + 1 high = mid - 1

Binary search limitations:

• The target object is an array structure, because the elements are randomly accessed through subscripts
• The array must be in order
• The array is too small to be suitable, just use sequential search
• It is not appropriate to have an array that is too long. An array requires continuous memory space, and an array that is too long is not conducive to storage.

Time complexity: O(logn)

Space complexity: O(1)

leetcode: https://leetcode-cn.com/problems/binary-search/solution/er-fen-cha-zhao-by-user7746o/