Skip to main content

C++ = Code for Binary Search

Who does Binary Search Work?
When describing an algorithm to a fellow human being, an incomplete description is often good enough. Some details may be left out of a recipe for a cake; the recipe assumes that you know how to open the refrigerator to get the eggs out and that you know how to crack the eggs. People might intuitively know how to fill in the missing details, but computer programs do not. That's why we need to describe computer algorithms completely.
In order to implement an algorithm in a programming language, you will need to understand an algorithm down to the details. What are the inputs to the problem? The outputs? What variables should be created, and what initial values should they have? What intermediate steps should be taken to compute other values and to ultimately compute the output? Do these steps repeat instructions that can be written in simplified form using a loop?
Let's look at how to describe binary search carefully. The main idea of binary search is to keep track of the current range of reasonable guesses. Let's say that I'm thinking of a number between one and 100, just like the guessing game. If you've already guessed 25 and I told you my number was higher, and you've already guessed 81 and I told you my number was lower, then the numbers in the range from 26 to 80 are the only reasonable guesses. Here, the red section of the number line contains the reasonable guesses, and the black section shows the guesses that we've ruled out:
In each turn, you choose a guess that divides the set of reasonable guesses into two ranges of roughly the same size. If your guess is not correct, then I tell you whether it's too high or too low, and you can eliminate about half of the reasonable guesses. For example, if the current range of reasonable guesses is 26 to 80, you would guess the halfway point, , or 53. If I then tell you that 53 is too high, you can eliminate all numbers from 53 to 80, leaving 26 to 52 as the new range of reasonable guesses, halving the size of the range.
For the guessing game, we can keep track of the set of reasonable guesses using a few variables. Let the variable  be the current minimum reasonable guess for this round, and let the variable  be the current maximum reasonable guess. The input to the problem is the number , the highest possible number that your opponent is thinking of. We assume that the lowest possible number is one, but it would be easy to modify the algorithm to take the lowest possible number as a second input.
Here's a step-by-step description of using binary search to play the guessing game:
  1. Let  and .
  2. Guess the average of  and , rounded down so that it is an integer.
  3. If you guessed the number, stop. You found it!
  4. If the guess was too low, set  to be one larger than the guess.
  5. If the guess was too high, set  to be one smaller than the guess.
  6. Go back to step two.
We could make that description even more precise by clearly describing the inputs and the outputs for the algorithm and by clarifying what we mean by instructions like "guess a number" and "stop." But this is enough detail for now.
Next up, we'll see how we can use binary search on an array, and discuss how to turn descriptions of algorithms into actual working code.


Code:
#include <iostream>
using namespace std;

int binarysearch(int array[5],int key)
{
    int start=0,end=5;
    while(start<=end){
        int middle=(start+end)/2;

        if (array[middle]==key){
            return middle;
        }
        else if (array[middle]>key){
            end=middle-1;
        }
        else if (array[middle]<key){
            start=middle+1;
        }
        else{
            return -1;
        }
    }
    return -1;
}


int main()
{
    int array[5]={1,2,3,4,5},key;
    cout<<"Enter the number to find in array : ";
    cin>>key;

    cout<<"The index of "<<key<<" is "<<binarysearch(array,key);

    
}

Result:




Comments

Post a Comment

Popular posts from this blog

C++ = Code for checking any digit palindrome number

Code no: 1 = Using only main function to perform task. #include <iostream> using namespace std; int main() { int number,original,digit,reverse=0; cout<<"Enter any number : "; cin>>number; original=number; while (number!=0) { digit=number%10; reverse=(reverse*10)+digit; number=number/10; } if (original==reverse) { cout<<"This "<<original<<" is Palindrome number."; } else { cout<<"The "<<original<<" is not Palindrome number."; } } Result: Code no: 2 = Using two functions to perform same task. #include <iostream> using namespace std; int isprime(int num) { int digit=0,reverse=0; while (num!=0) { digit=num%10; reverse=(reverse*10)+digit;  num/=10; } return reverse; } int main() { int num; cout<<"Enter any digit to find its sum = "; cin>>num;          int original=num;          if (i...
Post a Comment
Read more

C++ = Code to check number is a prime or not. If not find the nearest prime number.

Code:  #include <iostream> using namespace std; bool prime(int n) { if (n<=1) { return false; }        for (int i=2;i<=n/2;i++)    {       if (n%i==0)   {   return false;   }    }         return true; } int nearest(int n) { for (int i=n-1;i>=2;i--) { if (prime(i)) { return i; } } return 0; } int main () { int number; cout<<"Enter any number : "; cin>>number; if (prime(number)) { cout<<"The number is prime. "<<endl; }     else     {     cout<<"The entered number is compositive."<<endl;     cout<<"The nearest prime number will be "<<nearest(number)<<endl; } } Result:
Post a Comment
Read more

C++ = Code to check number wheater it is prime or not.

Code no 1= Without any other function with using another function. #include <iostream> using namespace std; int main() { int number; bool prime=true; cout<<"Enter any number : "; cin>>number; if (number<=1) { prime=false; } else { for (int i=2;i<number;i++) { if (number%i==0) { prime=false; break; } } } if (prime) { cout<<"The number is a prime number."<<endl; } else { cout<<"The number is not a prime number."<<endl; } } Code no: 2= With using another function #include <iostream> #include <cmath> using namespace std; bool prime(int n) { if (n<=1) { return false; } for (int i=2;i<n/2;i++) { if (n%i==0) { return false; } } return true; } int main() { int number; cout<<"Enter any number : "; cin>>number; if (prime(number)) { cout<<"The numbe...
Post a Comment
Read more