PythonScript/DataStructureAndAlgorithm/BinarySearch.md at master · chavarera/PythonScript · GitHub

History

159 lines (124 loc) · 3.62 KB

Raw

Binary Search

Introduction

Binary search also known as Half-Interval Search or logarithmic search .
Binary search is used to find the target value within a sorted array.

Simple Steps:

Binary search compares the target value to the middle element of the array.
If they are not equal, the half in which the target cannot lie is eliminated and the search continues on the remaining half,
again taking the middle element to compare to the target value,and repeating this until the target value is found.
If the search ends with the remaining half being empty, the target is not in the array.

Advantages

Binary search is faster than linear search except for small arrays.
The algorithm is faster compared to linear search.

Disadvantages

array must be sorted first to be able to apply binary search.
binary search is Slower than hash tables.
The worst case and the best case are nearly same for the binary search

Algorithm

Consider Variables

input Variable
lst   : Input List(sorted list)
number: Search ELement

Output Variable
result        : True if Element is Found Else False
middle(index) : -1 if element is not found else return index of search element.
iteration     : return Number of iteration

step 1 : set start variable to 0 and end variable to (length(lst)-1)

start=0
end=length(lst)-1

step 2 : if start is greater than end break the algorithm

step 3 : calculate middle variable

middle=(start+end)//2

step 4 : Check Following Conditions:

number==lst[middle]
- If the targe number is equal to list[middle] then search is complete .
- Break the loop
number>lst[middle]
- set the start to middle+1
```
start=middle+1
```
- Got to Step 2 and repeat
number<lst[middle]
- set the end to middle-1
```
end=middle-1
```
- Got to Step 2 and repeat

Program:

def BinarySearch(lst,number):
  '''Function Input
        lst: A Integer Element List
        number: The Number which Do you Want to Search
        
     Function Output:
        result: True if number is found else False
        middle(index): if element found then index else return -1 if element is not found
        iteration : Total No of Iteration Required
  '''
  
  result=False
  iteration=0
  length=len(lst)
  
  start=0
  end=length-1

  while start<=end:
    iteration+=1
    middle=(start+end)//2
    if lst[middle]==number:
      result=True
      break
    
    elif number>lst[middle]:
        start=middle+1
    elif number <lst[middle]:
        end=middle-1
  else:
      middle=-1
      
  return result,middle,iteration
  
#Driver Program  
#Simple List
lst=[1,2,3,4,5,6,7,8,9,10]

# Print Normal List
print(lst)
#Get Use Input From User
number=int(input("Enter Search Number:"))

#Call Search Function and save result in res and No of iteration in iteration
res,index,iteration=BinarySearch(lst,number)

#Print the Result
print("\nNumber In List: {} \nNumber Index :{} \nRequired iteration: {}".format(res,index,iteration))

Output for 2 Input

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Enter Search Number: 2

Number In List: True 
Number Index :1 
Required iteration: 2

Output For 11 Input

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Enter Search Number: 11

Number In List: False 
Number Index :-1 
Required iteration: 4

Output for 5 input

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Enter Search Number: 5

Number In List: True 
Number Index :4 
Required iteration: 1

Time Complexity

Best Case O(1)
Average Case O(log n)
Worst Case O(log n)

Space Complexity

O(1)