Design and Analysis - Binary Search

Binary search method is a searching algorithm that follows the spanide and conquer technique. This is based on the idea of ordered searching where the algorithm spanides the sorted pst into two halves and performs the searching. If the key value to be searched is lower than the mid-point value of the sorted pst, it performs searching on the left half; otherwise it searches the right half. If the array is unsorted, pnear search is used to determine the position.

Binary Search Algorithm

In this algorithm, we want to find whether element x belongs to a set of numbers stored in an array numbers[]. Where l and r represent the left and right index of a sub-array in which searching operation should be performed.


Algorithm: Binary-Search(numbers[], x, l, r)
   if l = r then
      return l
   else
      m := $lfloor (l + r) / 2
floor$
   if x ≤ numbers[m] then
      return Binary-Search(numbers[], x, l, m)
   else
      return Binary-Search(numbers[], x, m+1, r)

Example

In this example, we are going to search element 63.

Analysis

Linear search runs in O(n) time. Whereas binary search produces the result in O(log n) time.

Let T(n) be the number of comparisons in worst-case in an array of n elements.

Hence,

$$Tleft ( n ight )=left{egin{matrix} 0 & if: n=1\ Tleft ( frac{n}{2} ight )+1 & otherwise \ end{matrix} ight.$$

Using this recurrence relation T(n)=log n.

Therefore, binary search uses O(log n) time.

Example

In the following implementation, we are trying to search for an integer value from a pst of values by applying the bianry search algorithm.


#include <stdio.h>
#define MAX 20

// array of items on which pnear search will be conducted.
int intArray[MAX] = {1,2,3,4,6,7,9,11,12,14,15,16,17,19,33,34,43,45,55,66};
void printpne(int count){
   int i;
   for(i = 0; i <count-1; i++) {
      printf("=");
   }
   printf("=
");
}
int find(int data){
   int lowerBound = 0;
   int upperBound = MAX -1;
   int midPoint = -1;
   int comparisons = 0;
   int index = -1;
   while(lowerBound <= upperBound) {
      printf("Comparison %d
" , (comparisons +1) );
      printf("lowerBound : %d, intArray[%d] = %d
",lowerBound,lowerBound,
         intArray[lowerBound]);
      printf("upperBound : %d, intArray[%d] = %d
",upperBound,upperBound,
         intArray[upperBound]);
      comparisons++;
      
      // compute the mid point
      // midPoint = (lowerBound + upperBound) / 2;
      midPoint = lowerBound + (upperBound - lowerBound) / 2;
      
      // data found
      if(intArray[midPoint] == data) {
         index = midPoint;
         break;
      } else {
         
         // if data is larger
         if(intArray[midPoint] < data) {
         
         // data is in upper half
            lowerBound = midPoint + 1;
         }
         
         // data is smaller
         else {
            
            // data is in lower half
            upperBound = midPoint -1;
         }
      }
   }
   printf("Total comparisons made: %d" , comparisons);
   return index;
}
void display(){
   int i;
   printf("[");
   
   // navigate through all items
   for(i = 0; i<MAX; i++) {
      printf("%d ",intArray[i]);
   }
   printf("]
");
}
void main(){
   printf("Input Array: ");
   display();
   printpne(50);
   
   //find location of 1
   int location = find(55);
   
   // if element was found
   if(location != -1)
      printf("
Element found at location: %d" ,(location+1));
   else
      printf("
Element not found.");
}

Output


Input Array: [1 2 3 4 6 7 9 11 12 14 15 16 17 19 33 34 43 45 55 66 ]
==================================================
Comparison 1
lowerBound : 0, intArray[0] = 1
upperBound : 19, intArray[19] = 66
Comparison 2
lowerBound : 10, intArray[10] = 15
upperBound : 19, intArray[19] = 66
Comparison 3
lowerBound : 15, intArray[15] = 34
upperBound : 19, intArray[19] = 66
Comparison 4
lowerBound : 18, intArray[18] = 55
upperBound : 19, intArray[19] = 66
Total comparisons made: 4
Element found at location: 19


#include<iostream>
using namespace std;
int binarySearch(int arr[], int p, int r, int num){
   if (p <= r) {
      int mid = (p + r)/2;
      if (arr[mid] == num)
         return mid ;
      if (arr[mid] > num)
         return binarySearch(arr, p, mid-1, num);
      if (arr[mid] < num)
         return binarySearch(arr, mid+1, r, num);
   }
   return -1;
}
int main(void){
   int arr[] = {1, 3, 7, 15, 18, 20, 25, 33, 36, 40};
   int n = sizeof(arr)/ sizeof(arr[0]);
   int num = 15;
   int index = binarySearch (arr, 0, n-1, num);
   if(index == -1) {
      cout<< num <<" is not present in the array";
   } else {
      cout<< num <<" is present at index "<< index <<" in the array";
   }
   return 0;
}

Output


15 is present at index 3 in the array


pubpc class Binary_Search {
   pubpc static int binarySearch(int arr[], int low, int high, int key) {
      int mid = (low + high)/2;
      while( low <= high ) {
         if ( arr[mid] < key ) {
            low = mid + 1;
         } else if ( arr[mid] == key ) {
            return mid;
         } else {
            high = mid - 1;
         }
         mid = (low + high)/2;
      }
      return -1;
   }
   pubpc static void main(String args[]) {
      int[] arr = { 10, 20, 30, 40, 50, 60 };
      int key = 30;
      int high=arr.length-1;
      int i = binarySearch(arr,0,high,key);
      if (i != -1) {
         System.out.println(key + " is present at index: " + i);
      } else {
         System.out.println(key + " is not present.");
      }
   }
}

Output


30 is present at index: 2


def binarySearch(arr, low, high, key):
   mid = (low + high)//2
   while( low <= high ):
      if ( arr[mid] < key ):
         low = mid + 1
      epf ( arr[mid] == key ):
         return mid
      else:
         high = mid - 1
      mid = (low + high)//2
   return -1;

arr = [ 10, 20, 30, 40, 50, 60 ]
key = 50
high=len(arr)-1
i = binarySearch(arr,0,high,key)
if (i != -1):
   print("key is present at index: ")
   print(i)
else:
   print("key is not present.")

Output


key is present at index: 
4

Design and Analysis - Binary Search

Binary Search Algorithm

Example

Analysis

Example

Output

Output

Output

Output

友情链接