1 of 18

PROBLEM SOLVING TECHNIQUES

By

​

​

Dept. of CSE

PVPSIT, Kanuru.

​

​

PRASAD V. POTLURI SIDDHARTHA INSTITUTE OF TECHNOLOGY

2 of 18

  • Problem: Given an element x and a set of data that is in strictly ascending numerical order find whether or not x is present in the set.
  • Algorithm development: The problem of searching an ordered list such as a dictionary or telephone directory occurs frequently in computing.
  • Consider an example:
  • A non-computing experience of searching ordered data.
  • How we use the telephone directory to look up someone’s phone number (perhaps Mr J. K. Smith’s number).
  • One way to find his number would be to start at page 1 of the telephone book and progress through page-by-page until we are successful.
  • Personal experience tells us that this method is far too slow and that instead we use a completely different approach to solve the problem.

B. Vinay Kumar

Tuesday, March 8, 2022

BINARY SEARCH

PVPSIT (Autonomous)

Problem Solving Techniques

3 of 18

  • In looking for Mr Smith’s number we certainly do not start looking near the front of the directory.
  • Instead we would probably open the directory at a page somewhere more than two-thirds of the way through.
  • From our current position, depending on the name we had encountered, we would apply the same strategy again although most probably on a smaller scale.

B. Vinay Kumar

Tuesday, March 8, 2022

PVPSIT (Autonomous)

Problem Solving Techniques

4 of 18

B. Vinay Kumar

Tuesday, March 8, 2022

PVPSIT (Autonomous)

Problem Solving Techniques

5 of 18

  • Let us now consider a specific example in order to try to find the details of the algorithm needed for implementation.

​

​

​

​

  • Suppose we are required to search an array of 15 ordered elements to establish if x = 44 is present and, if so, the position that it occupies in the array.
  • We start by examining the middle value in the array.

middle := n div 2

​

B. Vinay Kumar

Tuesday, March 8, 2022

PVPSIT (Autonomous)

Problem Solving Techniques

6 of 18

  • middle:= (lower + upper) div 2.
  • This gives a[middle] = a[8] = 39.
  • Since the value we are seeking (i.e. 44) is greater than 39 it must be somewhere in the range a[9] … a[15].
  • That is, a[9] becomes the lower limit of where 44 could be.
  • That is, lower : = middle + 1.
  • We then have:

B. Vinay Kumar

Tuesday, March 8, 2022

PVPSIT (Autonomous)

Problem Solving Techniques

7 of 18

​

​

  • When a[12] is examined it is established that 44 is less than a[12].
  • It follows that 44 (if it is present) must be in the range a[9] … a[11].
  • Accordingly the upper limit becomes one less than middle value, i.e.
  • upper := middle – 1
  • We then have:

​

B. Vinay Kumar

Tuesday, March 8, 2022

PVPSIT (Autonomous)

Problem Solving Techniques

8 of 18

  • From this we see that with each comparison either the lower limit is increased or the upper limit is decreased.
  • With the next comparison we find the value we are seeking and its position in the array.
  • That is, in just 3 comparisons we have located the value we wanted.

B. Vinay Kumar

Tuesday, March 8, 2022

PVPSIT (Autonomous)

Problem Solving Techniques

9 of 18

B. Vinay Kumar

Tuesday, March 8, 2022

PVPSIT (Autonomous)

Problem Solving Techniques

10 of 18

  • Assume:
  • A ← sorted array
  • n ← size of array
  • x ← value to be searched
  • pos ← -1
  • Step 0: Start
  • Step 1: Set lowerBound = 1
  • Step 2: Set upperBound = n
  • Step 3: Repeat Step 3.1, 3.2 till lowerBound<= upperBound
  • Step 3.1 midIndex = (lowerBound + upperBound)/2
  • Step 3.2 if x = A[midIndex]) then pos = midIndex, go to Step 4.

else if (item > A[midIndex]) then lowerBound = midIndex + 1

else upperBound = midIndex - 1

B. Vinay Kumar

Tuesday, March 8, 2022

Algorithm: (As Per Class Room Discussion)

PVPSIT (Autonomous)

Problem Solving Techniques

11 of 18

  • Step 4: if pos <> -1 then print("Element is present at index” pos)

else print("Not found")

Step 5: Stop

B. Vinay Kumar

Tuesday, March 8, 2022

PVPSIT (Autonomous)

Problem Solving Techniques

12 of 18

  • a[1..n] Sorted Array
  • read (x)
  • lower=1, upper = n
  • while (lower < upper) do

begin

mid=(lower + upper) div 2

If x > a[middle] then

lower := middle + 1

else

upper := middle

end

  • found := (a[lower] = x)

B. Vinay Kumar

Tuesday, March 8, 2022

Pseudocode: (As per Text Book)

PVPSIT (Autonomous)

Problem Solving Techniques

13 of 18

B. Vinay Kumar

Tuesday, March 8, 2022

PVPSIT (Autonomous)

Problem Solving Techniques

14 of 18

  • Applications:
  • Only for sorting data in which a small percentage of elements are out of order.

B. Vinay Kumar

Tuesday, March 8, 2022

PVPSIT (Autonomous)

Problem Solving Techniques

15 of 18

B. Vinay Kumar

Tuesday, March 8, 2022

PVPSIT (Autonomous)

Problem Solving Techniques

16 of 18

B. Vinay Kumar

Tuesday, March 8, 2022

PVPSIT (Autonomous)

Problem Solving Techniques

17 of 18

  • Worst complexity: O(log n)
  • Average complexity: O(log n)
  • Best complexity: O(1)
  • Space complexity: O(1)

B. Vinay Kumar

Tuesday, March 8, 2022

PVPSIT (Autonomous)

Problem Solving Techniques

18 of 18

  • Animation

B. Vinay Kumar

Tuesday, March 8, 2022

PVPSIT (Autonomous)

Problem Solving Techniques