Example details of C++ binary search of binary search algorithm

The example of this paper describes the C++2 cent search (half search) algorithm. I will share it with you for your reference as follows:

2 points search also known as broken half search, the advantage is less times, search speed, the average performance is good; The disadvantage is that it requires the waiting table to be an ordered table, and it is difficult to insert and delete.

Therefore, the binary search method is suitable for frequent ordered lists that do not change frequently.

2. Look for ideas

First, assuming that the elements in the table are arranged in ascending order, the keywords of the records in the middle of the table are compared with the search keywords. If they are equal, the search is successful.

Otherwise, the middle position record is used to divide the table into two sub-tables. If the keyword of the middle position record is greater than the search keyword, the first sub-table will be searched one step ahead, otherwise, the second sub-table will be searched one step ahead.

Repeat the process until you find a record that meets the criteria to make the lookup successful, or until the subtable does not exist and the lookup is unsuccessful.

Basic algorithm C language implementation code:

int binary_search(int arr[], int len, int elem)
{
  int low = 0;
  int high = len - 1;
  while (low <= high)
  {
    int mid = (low + high) / 2;
    if (elem == arr[mid]){   // Equal, return mid
      return mid;
    }
    else if (elem > arr[mid]){
      low = mid + 1;  // If the element is larger than the middle element of the interval, take the bottom of the middle element of the interval 1 The starting position of the new interval is 1 element 
    }
    else{
      high = mid - 1; // The element is smaller than the middle element of the interval, so let's take the top of the middle element of the interval 1 As the end of the new interval 
    }
  }
  return -1;
}

Add a program instance that checks if it is an ordered ordinal group

#include <iostream>
using namespace std;
int binary_search(int arr[], int len, int elem)
{
  int low = 0;
  int high = len - 1;
  while (low <= high)
  {
    int mid = (low + high) / 2;
    if (elem == arr[mid]){
      return mid;
    }
    else if (elem > arr[mid]){
      low = mid + 1;
    }
    else{
      high = mid - 1;
    }
  }
  return -1;
}
// Check if the order is in order 
int is_sorted(int arr[], int len)
{
  int sorted = 1;
  for (int i = 0; i < len - 1; i++)
  {
    sorted = sorted && arr[i] <= arr[i + 1];
  }
  return sorted;
}
int main()
{
  int arr[] = { 1, 3, 5, 7, 9, 11, 12, 15, 18, 23, 25, 26 };
  int len = sizeof(arr) / sizeof(int);
  int pos;
  int sorted = is_sorted(arr, len);
  if (sorted)
  {
    pos = binary_search(arr, len, 26);
    cout << "pos = " << pos << endl;
  }
  system("pause");
}

Operation results:

pos = 11
 Please press any key to continue . . .

I hope this article has helped you with C++ programming.