Home PC Games Linux Windows Database Network Programming Server Mobile  
           
  Home \ Programming \ Implement binary search algorithm in C language     - Installed FFmpeg 2.6.3 on Ubuntu / Debian / Fedora system (Linux)

- VirtualBox modify the size of the virtual machine disk VDI (Linux)

- Cobbler batch install Ubuntu / CentOS system (Linux)

- Oracle Database ORA-01555 snapshot too old (Database)

- Golang use Oracle database on Ubuntu 14.04 (Linux)

- Binary Packages Golang (Linux)

- Squid proxy server configuration under Linux (Server)

- Installation Sublime Text 3 (Build 3065) text editor in Ubuntu (Linux)

- GAMIT 10.50 installed in Ubuntu 12.04 system (Linux)

- Teach you how to ensure password security under the Linux operating system (Linux)

- C # C ++ Java interface type conversion (Programming)

- Linux basis: a comprehensive study pwd command (Linux)

- Database start listening TNS-12537, TNS-12560 error (Database)

- Shell scripts to copy all directories under the current directory of a certain type of file to the same directory (Linux)

- JavaScript event handling Detailed (Programming)

- The difference between statement and preparedStatement of the jdbc (Database)

- Create a custom pixel format based on an existing image data BufferedImage (Programming)

- To share some very useful Vim command (Linux)

- Oracle RAC 10.2.0.5 upgrade to 11.2.0.4 problems encountered (Database)

- C ++ in the elimination Wunused (Programming)

 
         
  Implement binary search algorithm in C language
     
  Add Date : 2018-11-21      
         
         
         
  Binary search algorithm thinking is very simple, it is an ordered sequence of binary search, where I use a binary search integer array order. If implemented in C, then we need to pay attention to the following aspects:

1. How to determine the lookup is completed, the return value is defined meanings, define exit loop condition

2. How to deal with border issues, such as 123 of this sequence, when we're looking for 1 or 3, it will make the program appear BUG

3. For the number of columns, we usually use plastic storage under standard, remove the standard binary search if the intermediate numbers, what kind of problem occurs? Whether these problems will affect our search, if the problem is how to avoid?

Typically, as a beginner, I think even a binary search is too simple, not worth mentioning, the recent reflection, binary search algorithm for the requirements of the theory is not very high, but if it is put into the feasibility of the program code , then we need to think about many of the details, otherwise write the code is error-prone.

How to solve the first problem, because we understand the idea of ​​binary search is actually a binary search, to have the left margin and right margin we can determine the intermediate element, when the left edge of the right boundary coincides with the time, then find the object becomes an element, if it is not to find an object request, then look in the collection will not have the required elements. So that we clearly define the parameters needed to come out, and quit the Find conditions. We need a left border and right border, as well as the middle element, if the right margin smaller (larger than the left and right) than the left margin when the loop exits, returns an exception. If not, perform a lookup statement.

Here's how to design it to find the statement, if combined with the second and third question, we can readily write the code:

while (left <= right)
{
    mid = (left + right) / 2;
    if (x> mid)
    left = mid;
    else if (x     right = mid;
    else
    return mid;
}
return error;

Obviously doing so it is too good, according to the ideas of mathematics, this is simply not eligible borders, considering the C language will be automatically discarded plastic decimals, then the left boundary is entirely possible that we write but right boundary is never to take, if the intermediate value taken to a non-integer, it will affect other aspects of our search results, the answer is no, if discarded automatically generated status decimal, only to find only affect us in an ordered sequence of elements in a position to find the sub-segment length, and will not affect our search results, if you want to solve the border issue, we can make partial segment generated boundary shift, since the mid element has been judged too, so when we segment boundary segments can discard mid element, so that the border is mid + 1 or mid-1, and we will complete the binary search of an array of integers, codes are as follows:

#include // binary search algorithm that is the test case
int BinySerch (int * arr, int x, int lengh) // design parameters, as is the integer array, so we have to pass him
{// Array length downgrade occur when the Senate otherwise
int left = 0, right = lengh - 1;
int mid;
while (left <= right)
{
mid = left + (right - left) / 2;
if (x {
right = mid - 1;
}
else if (x> arr [mid])
{
left = mid + 1;
}
else
{
return mid;
}
}
return -1;
}
int main () // test case
{
int x = 0;
int arr [11] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int lengh = sizeof (arr) / sizeof (arr [0]);
for (int i = 0; i <12; i ++)
{
printf ( "% d", BinySerch (arr, i, lengh));
}
system ( "pause");
return 0;
}
     
         
         
         
  More:      
 
- Oracle online redefinition (Database)
- Oracle 10g in the unique and index problems (Database)
- ASM Disk Space Check (Database)
- React Native (Programming)
- How to test your MongoDB application upgrade? (Database)
- Why not use the ifconfig command under RedHat Linux 5 (Linux)
- SSH without password (Linux)
- Ubuntu 15.10 under Python + Apache + CGI fully configured (Server)
- Sublime Text 3 best features, plug-ins and settings (Linux)
- Linux itself disguised illusion strengthen security (Linux)
- GCC and gfortran write MEX program (Matlab2012a) under Ubuntu 14.04 (Programming)
- Linux SSH remote connection service slow Solutions (Linux)
- DB2 table space is redirected to restore the database combat (Database)
- Oracle 12c In-Memory Study (Database)
- Linux (CentOS) directory file management and file system file compression packing (Linux)
- Advanced network security tips Linux backdoor Technology and Practice (Linux)
- Linux desktop system using the remote server in clear text ssh password (Server)
- VMware virtual machine can not start VMnet0 no Internet access and other issues (Linux)
- Linux more command Detailed (Linux)
- MySQL Server Time Synchronization Problem (Database)
     
           
     
  CopyRight 2002-2022 newfreesoft.com, All Rights Reserved.