Binary Search Algo

This is a discussion on Binary Search Algo within the C++ Programming forums, part of the General Programming Boards category; My Code is'nt able to find the index value if the 1st or the 2nd element of the array is ...

  1. #1
    Registered User Sid_TheBeginner's Avatar
    Join Date
    Jun 2012
    Location
    India
    Posts
    19

    Exclamation Binary Search Algo

    My Code is'nt able to find the index value if the 1st or the 2nd element of the array is checked for. Here's my code.
    Also i want to exit on pressing 'x' For now, I'm using -1 to exit.

    Code:
    #include<iostream>
    #include<ctype.h>
    using namespace std;
    int main()
    {
    int arr[] = {1, 4, 5, 6, 9, 14, 21, 23, 28, 31, 35, 42, 46, 50, 53, 57, 62, 63, 65, 74, 79, 89, 95};
    int value;
    for(int i = 0; i < 23; i++)
    cout << arr[i] << " ";
    cout << endl;
    while(1)
    {
    cout << "Enter seach value(-1 to exit): ";
    cin >> value;
    if(value == -1)
    {
    cout << "Exiting..\n";
    break;
    }
    int beg = 0;
    int end = 23;
    for(beg = 0; beg < 23; beg++)
    {
    int middle = (beg+end)/2;
    if(value == arr[middle])
    {
    cout << "Its at location " << middle << endl;
    break;
    }
    else if(value > arr[middle])
    end = middle + 1;
    else if(value < arr[middle])
    end = middle - 1;
    else
    cout << "Element Not found\n";
    }
    }
    }
    Thanks,
    --Sid
    Last edited by Sid_TheBeginner; 06-25-2012 at 01:04 AM. Reason: please tell me how to exit using 'x' rather than -1

  2. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    You're completely missing your indentation here. For reference, this is how you indent code:
    Code:
    #include<iostream>
    #include<ctype.h>
    using namespace std;
    int main()
    {
        int arr[] = {1, 4, 5, 6, 9, 14, 21, 23, 28, 31, 35, 42, 46, 50, 53, 57, 62, 63, 65, 74, 79, 89, 95};
        int value;
        for(int i = 0; i < 23; i++)
            cout << arr[i] << " ";
        cout << endl;
        while(1)
        {
            cout << "Enter seach value(-1 to exit): ";
            cin >> value;
            if(value == -1)
            {
                cout << "Exiting..\n";
                break;
            }
            int beg = 0;
            int end = 23;
            for(beg = 0; beg < 23; beg++)
            {
                int middle = (beg+end)/2;
                if(value == arr[middle])
                {
                    cout << "Its at location " << middle << endl;
                    break;
                }
                else if(value > arr[middle])
                    end = middle + 1;
                else if(value < arr[middle])
                    end = middle - 1;
                else
                    cout << "Element Not found\n";
            }
        }
    }
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    Right, now I can read your code.
    A binary search does not involve a loop over all items, so looping form 0 to 23 means it is not a binary search. It's like a mashup of linear search and binary search, and consequently does not work as either.

    Having said that, it can be fixed by changing two lines. I'm not telling which two yet.
    Fix up some other things first...
    That magic number 23 has to go. instead use sizeof(arr)/sizeof(arr[0]). That calcuates the size of the whole array divide by the size of one item, giving the total number of items.

    Lines 34 and 35 are a waste of time. How can value be not equal to arr[middle], but also not less than it and not greater than it?
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  4. #4
    Registered User Sid_TheBeginner's Avatar
    Join Date
    Jun 2012
    Location
    India
    Posts
    19
    Thanks for your reply Sir. Indentation was fine before pasting it here.
    So my logic is terribly wrong?!! Maybe I should slow down my learning speed. Can you please recommend any good book to learn C++ from?

  5. #5
    Registered User manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    Kolkata@India
    Posts
    2,523
    Quote Originally Posted by Sid_TheBeginner View Post
    So my logic is terribly wrong?!!
    There is right and wrong to consider, no middle ground.
    Try understanding the logic first, and the code will automatically be correct (apart from syntax errors, which are easily corrected).

    Can you please recommend any good book to learn C++ from?
    C++ Book Recommendations
    The Definitive C++ Book Guide and List - Stack Overflow
    Manasij Mukherjee | gcc-4.9.2 @Arch Linux
    Slow and Steady wins the race... if and only if :
    1.None of the other participants are fast and steady.
    2.The fast and unsteady suddenly falls asleep while running !



Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Binary Search Tree-search method help?
    By shocklightning in forum C++ Programming
    Replies: 5
    Last Post: 03-25-2012, 11:57 PM
  2. Difference Between A Linear Search And Binary Search
    By ImBack92 in forum C Programming
    Replies: 4
    Last Post: 05-12-2011, 09:47 AM
  3. A Binary Search Tree of... Binary Search Trees...
    By SlyMaelstrom in forum C++ Programming
    Replies: 5
    Last Post: 12-10-2005, 02:12 PM
  4. Search Engine - Binary Search Tree
    By Gecko2099 in forum C Programming
    Replies: 9
    Last Post: 04-17-2005, 03:56 PM
  5. binary search and search using binary tree
    By Micko in forum C++ Programming
    Replies: 9
    Last Post: 03-18-2004, 10:18 AM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21