Binary Search

• The binary search algorithm can be used with only a sorted list of elements.
• Binary search follows divide and conquer approach in which, the list is divided into two halves.

Algorithm:

1. This search process starts comparing the search element with the middle element in the list

2. If both are matched, then the result is "element found".

3. Otherwise, we check whether the search element is smaller or larger than the middle element in the list.

4. If the search element is smaller, then we repeat the same process for the left sublist of the middle element.

5. If the search element is larger, then we repeat the same process for the right sublist of the middle element. 

6. if that element doesn't match with the search element, then the result is "Element not found in the list".

Example: 

1.The array in which searching is to be performed is:

Let, x= 4 element to be searched.

2. Set two pointers low and high at the lowest and the highest positions respectively.  Ie.,  low= 0 and high =6

3. Find the element  mid of the array ie. ([low+high])/2 =3 ie mid at 3rd location

4. If x == arr[mid], then return mid. Else, compare the element to be searched with mid.

Ie. 4==6 

5.  If x>arr[mid]  compare x with middle element of  the elements of the right side of mid. Ie 4>6….? 

This is done by setting low to low= mid+1

6. Else, compare x with the middle of the elements on the left side of mid. 

7. Repeat steps 3 to 6 until low meets high

8. x=4 is found 

Pseudo Code:

This can be implemented in two ways which are discussed below.

1. Iterative Method

2. Recursive Method

• Iterative Method

do until the pointers low and high meet each other.

mid = (low + high)/2

if (x == arr[mid])

    return mid

else if (x > A[mid]) // x is on the right side

    low = mid + 1

else                     // x is on the left side

   high = mid - 1

• Recursive Method

The recursive method follows the divide and conquer approach.

binarySearch(arr, x, low, high)

  if low > high

      return False 

  else

      mid = (low + high) / 2 

      if x == arr[mid]

           return mid

      else if x < data[mid]        // x is on the right side

           return binarySearch(arr, x, mid + 1, high)

      else                       // x is on the right side

          return binarySearch(arr, x, low, mid - 1)

This is done by setting high to high= mid-1.   ie.  high = 3-1=2

• Time Complexity:

• Linear search time complexity is O(n).

• Where Binary search has O(logn).

Program:

L=[]
def get():
    n=int(input("Enter no of students"))
    for i in range(n):
        no=int(input("Enter no"))
        L.append(no)

def dis():
    for i in L:
        print(i,end=" ")
    print("\nDisplaying ascending order")
    L.sort()
    print(L)

def search():
    key=int(input("Enter key to be search"))
    low=0
    high=L.index(L[-1])
    print("Low=",low)
    print("High=",high)
    i=-1
    while(i<len(L)):
        i=i+1
        mid=(low+high)//2
        if(L[mid]==key):
            print("Key is found at ", mid, "location")
            exit(code=True)
        else:
            if key>L[mid]:
                low=mid+1
            else:
                high=mid-1
        if(i==len(L)):
            print("Key not found")



get()
dis()

search()