A simple example of binary search in C language programming

The array v is in ascending order. The array v has n=20 elements. There is an element x in the array. How do I know where x is in the array?
One common solution to this problem is the two-point lookup. Here's the program:

#include <stdio.h>
int binsearch(int x, int v[], int n);
main()
{
  int i, result, n;
 int wait;
  
  int x = 17; //  The value to look for 
 int v[19]; //  define 1 An array 
 //  Assign a value to an array 
 for(i = 0; i < 20; ++i)
   v[i] = i;
 /**
 for(i = 0; i < 20; ++i)
 printf("%d \n", v[i]);
 */
 n = 20;
 result = binsearch(x, v, n);
 printf("%d", result);
 scanf("%d", &wait);
}
int binsearch(int x, int v[], int n)
{
 int low, high, mid;
 low = 0;
 high = n - 1;
 while (low <= high)
 {
 mid = (low + high) / 2;
 if(x < v[mid])
  high = mid - 1;
 else if (x > v[mid])
  low = mid + 1;
 else
  return mid;
 //  See how many times the loop executes 
 printf("mid = %d, low = %d, high = %d \n", mid, low, high);
 }
 return -1;
}

1, 2 points search method

      two-point search has an important premise: the sequence to be searched must be ordered.

      assumes that the sequence of elements is in ascending order, and compares the keyword recorded in the middle of the sequence with the search keyword. If the two are equal, the search succeeds. Otherwise, the intermediate position record is used to divide the sequence into two subsequences, the former and the latter. If the keyword of the intermediate position record is greater than the search keyword, the former subsequence will be found in step 1; otherwise, the latter subsequence will be found in step 1. Repeat the procedure until a record that satisfies the condition is found, the search succeeds, the index of the element in the sequence is returned, or until the subsequence does not exist, the search fails, and -1 is returned.

int find2(int *array,int n,int val) 
{ 
  if (n<=0) 
  { 
    return -1; 
  } 
 
  int begin=0,end=n-1,mid; 
  while(begin<=end)       
  { 
    mid=(begin+end)/2; 
    if (array[mid]==val) 
      return mid; 
    else if(array[mid]>val) 
      end=mid-1; 
    else 
      begin=mid+1; 
  } 
 
  return -1; 
} 

2. Find with a two-point search tree

      first creates a two-point search tree. We know that the two-point search tree is characterized by the values of the left subtree are smaller than the root node, the values of the right subtree are larger than the root node, and the elements obtained by the middle order traversal of the two-point search tree are sorted.

//2 The fork finds the tree data structure  
typedef struct Btree 
{ 
  int data; 
  Btree *left; 
  Btree *right; 
}*PBTree; 
 
// create 2 The fork finds the tree and returns the root node of the tree  
PBTree CreateBTree(int *array,int n) 
{ 
  PBTree root=new Btree; 
  root->data=array[0]; 
  root->left=NULL; 
  root->right=NULL; 
 
  PBTree current,back,pNew; 
  for (int i=1;i<n;i++) 
  { 
    pNew=new Btree; 
    pNew->data=array[i]; 
    pNew->left=pNew->right=NULL; 
    current=root; 
    while(current!=NULL)  // Find the right insertion location  
    { 
      back=current; 
      if(current->data>array[i]) 
        current=current->left; 
      else 
        current=current->right; 
    } 
    if(back->data>array[i]) 
      back->left=pNew; 
    else 
      back->right=pNew; 
  } 
 
  return root; 
} 
 
// using 2 The fork lookup tree performs a recursive lookup  
bool find3(PBTree root,int val) 
{ 
  if (root==NULL) 
    return false; 
  if (root->data==val) 
    return true; 
  else if(root->data>val) 
    return find3(root->left,val); 
  else 
    return find3(root->right,val); 
} 

3, summarize

      2 sub search has very strict constraints (the sequence must be ordered);

      automatically creates an "ordered tree" using a two-point lookup tree.

      does not consider the establishment time of two-fork search tree, the efficiency of the two is 1, O (logn).