编程知识 cdmana.com

Xiaobai understands the binary query algorithm

Recently, we've done a lot of algorithms , I found myself forgetting a lot ; Quickly brush a few times to consolidate the memory , By the way, I would like to make a simple sharing , I hope I can help some friends ！

One . Introduction

Binary query is a query algorithm with high efficiency for query elements , Also known as “ The binary algorithm ”.

Two . Premise

One of the most important preconditions for binary queries is The set or sequence to query It has to be Orderly

3、 ... and . The query process

The process of binary query ：

1）. Determine a query value

2）. Find the middle value in the sequence

3）. Compare the query value with the intermediate value , Two results ：

》 identical , It's worth finding

》 inequality , Zoom out 1/2 The scope of , Repetition 2）.3） To

Four . illustration （ Picture source Baidu ）

5、 ... and . Code implementation

The idea of flying in the sky , In the end, it has to be realized on the ground . Or it's blowing water , Use language Java To achieve , There are two ways ： Recursion and while Turn around .

Recursive implementation of binary query

```    /**
*      Using recursion to implement binary query
* @param sortedArr： An ordered array of queries
* @param key： Query value , Nowadays, most people call them keywords , use key Express
* @param low： Starting point
* @param high： The end
* @return
*/
public static boolean binarySearchByRecursion(int[] sortedArr, int key, int low, int high) {

/**
*      Check ：
*         1. If  key > sortedArr[high], The value must not be found
*         2. If  key < sortedArr[low], The value must not be found
*         3. If low > high, Logic doesn't hold , There is no intermediate value .
*/
if(key < sortedArr[low] || key > sortedArr[high] || low > high) {
return false;
}

/**
*      Get the index of the middle value , There are two results ：
*         1. Odd number .java The default is rounded down , It's OK to take an odd number as an intermediate index
*         2. Even number . Take even numbers   perhaps   Even number +1  Will do . Even numbers are taken here
*/

int mid = (high+low)/2;    // Get the index of the middle value

/*
*      Determine the query value and intermediate value
*         1.  Query value  >  Median , The starting point narrows to the right , Call this method back
*         2. Query value  <  Median , The end point narrows to the left , Call this method back
*         3. Query value  =  Median , Value found
*/

if(key == sortedArr[mid]) {    // Query value  =  Median
return true;    // return true
}else if(key > sortedArr[mid]) {    // Query value  >  Median
// The starting point narrows the scope
low = mid + 1;
// Recursively calls this function
return binarySearchByRecursion(sortedArr,key,low,high);
}else if(key < sortedArr[mid]){    // Query value  <  Median
// The end point narrowed down
high = mid - 1;
// Recursively calls this function
return binarySearchByRecursion(sortedArr,key,low,high);
}

return false;
}```

main Method test ：

```    public static void main(String[] args) {
// Prepare an ordered array
int[] sortedArr = new int[] {1,2,3,4,5,6,7,8,9,10,11,12,13,14};

// Prepare a query value
int key = 2;
// Prepare the starting and ending positions
int low = 0;
int high = sortedArr.length-1;

// Calling the binary query method returns a brin identifier ,true -  On behalf of finding ,false The representative couldn't find
boolean result = binarySearchByRecursion(sortedArr,key,low,high);

// Printing results
if(result) {
System.out.println(" There is... In the sequence "+key);
}else {
System.out.println(" There is no... In the sequence "+key);
}

}```

while Implement binary query

```    public static boolean binarySearchByWhile(int[] sortedArr, int key, int low, int high) {
/**
*      Check ：
*         1. If  key > sortedArr[high], The value must not be found
*         2. If  key < sortedArr[low], The value must not be found
*         3. If low > high, Logic doesn't hold , There is no intermediate value .
*/
if(key < sortedArr[low] || key > sortedArr[high] || low > high) {
return false;
}

while(low<=high) {    // Meet the starting point <= The end can go on , Because there is a middle value between the two
// Get the middle subscript
int mid = (high+low)/2;

// if key = sortedArr[mid]
if(key == sortedArr[mid]) {
return true;
}else if(key > sortedArr[mid]) {    // if key > sortedArr[mid]
// Narrow the starting point
low = mid + 1;
}else if(key < sortedArr[mid]){        // if key < sortedArr[mid]
// Narrow the finish line
high = mid -1;
}
}
// No return found false
return false;
}```

main Method test ：

```    public static void main(String[] args) {
// Building an ordered array
int[] sortedArr = new int[] {1,2,3,4,5,6,7,8,9,10};
// Create query values
int key = 10;
// Establish a starting point and an end point
int low = 0;
int high = sortedArr.length-1;
// Call binary query method , return true On behalf of finding , Otherwise, we can't find
boolean result = binarySearchByWhile(sortedArr,key,low,high);
// Printing results
if(result) {
System.out.println(" There is... In the sequence "+key);
}else {
System.out.println(" There is no... In the sequence "+key);
}
}```