Skip to main content

Posts

Showing posts from March, 2021

Binary Search

 Problem: We have a sorted array and a key element, we need to find out if the key element is present in the array. If it exists return the index of that element or return -1 if it doesn't exist. If the array has repeated elements, the order of the index is not important. Example: Pseudocode: Step 1: Initialise low = 0, high = array.count - 1 Step 2: Run a loop until low <= high Step 3: Compute middle index             middle  = (low + high) / 2 Step 4: If array[middle] == x, we found the index, then             return x Step 5: If  x < array[middle], x lies in the first half of the array, then             high = middle - 1             repeat from step 2 Step 6: If x > array[middle], x lies in the seco