Binary Search

[Former Member]

Hi All,

I need a very clear information for two questions

1. For binary search , why we need to sort the table before reading the table?.

2.For using binary search,when reading the table with the key fields ,whether the key fields needs to be in order like one after another?.

Anyone can help me on this.

Thanks,

Shri.

[Former Member]

HI,

in binary search it compares the given key with the middle one if it is less than middle it search in first half else in second half.it search like that till to get ...

so key fields must be in sort.

regards,

ananth

[Former Member]

Hi Ram

for binary search you have to sort the table becoze it divide the table in two parts and then search that where is the key field (either in left portion or in right ) , say in left , then it agian divide left in two portion and continue as above until the key found.

rgds

Deepak

[ashok_kumar24]

Hi SHri Ram

Binary Search has the following advantages

O(log N) can be MUCH better than O(N)

For large values of N, differences in efficiency are dramatic. For example, a linear search of an array requires n/2 comparisons on the average. If the array is sorted, it's possible to do a binary search with an average of log base 2 comparisons. For small values of n this is not an important difference. For example, for 32 items it takes 16 comparisons for linear search vs 5 for a binary search. The extra 11 comparisons are negligible.

In contrast to this, if n is a million, a linear search requires 500,000 comparisons vs 20 comparisons for binary search. This is significant, but there are other issues. For example, inserting or deleting in a sorted list is an O(N) operation because, on the average, half of the elements that have to be moved, so for frequent updates there is much less advantage to a sorted array. Binary search is also not possible on a linked list because random access is required.

Binary search trees: O(log N) search and insert

Because insertion in a tree is a matter of changing links and not moving data, binary search trees have the speed advantages of sorted arrays for searching plus fast inserting (O(log n) to find the insertion point and O(1) to insert). A fairly well balanced tree can be maintained with so-called red-black trees.

Good Luck and thanks

AK

[Former Member]

Hi Shri Ram,

First Binary Search means it sorts the data in the following way: Firstly it divides the data into two equal havlves and starts comparing the fields up and down of it and then it sorts them accordingly.

So , to increase your program efficiency and increase the performance, it is better to sort the table data so that the binary search becomes fast and efficient.

Hope this resolves your query.

Reward all the helpful answers.

Regards

[Former Member]

hi Shri Ram,

if u sort the <itab> , then it can arrange the fields in ascending order with specified key fields, after that if u read that <itab> with binary search, the search becomes easy because Binary search means it divides by 2 on all records then it search(if total records are 1000 in <itab> then binary search divides by 2, then two parts avbl 500 and 500). Now in avbl two parts it avoids one part and divides 500 by 2 then it searchs and so on..... for this purpose we should sort <itab> in order then we can get our records easily.

regards..

seshu.

[Former Member]

hi

binary search is a concept which searches your table in a different way...

we have to sort the fields before doing binary search bcoz it searches with respect to the key field..

for example, the data i have in the table (which is sorted by the search field) is..

1

5

6

22

55

56

79

90

if i search the record 6, it divides the table into two parts and search whether the record is in first part or second..

so now it has 1, 5, 6, 22. it again divides that into two parts...

now it has 6 & 22. if it again divides into two parts... it gets the value 6.

so by 4 searches it gets the record instead of searching each record (as in linear search).

that is the reason it has to be sorted.

if the table is not sorted..

1

55

90

5

22

6

79

56.

the binary search cannot work properly.

hope this helps

thx

pavan

*pls mark for helpful answers

[Former Member]

Hi Shri,

For doing the Binary Search, we must have to sort it first, else we cannot able to search it successfully. If it is sorted(in ascendung or descending) then we can easily identify the middle field and then we can easily find the key field.

Thanks and regards

Vipin Das