Binary search algorithm analysis

Basic framework:

int binarySearch(int[] nums, int target) {
    int left = 0, right = ... ;while(...). {int mid = (right + left) / 2;
        if (nums[mid] == target) {
            ...
        } else if (nums[mid] < target) {
            left = ...
        } else if(nums[mid] > target) { right = ... }}return. ; }Copy the code

Finding a number (basic binary search)

This scenario is the simplest and probably the most familiar: search for a number and return its index if it exists, otherwise return -1.

int binarySearch(int[] nums, int target) {
    int left = 0; 
    int right = nums.length - 1; / / note
    while(left <= right) {
        int mid = (right + left) / 2;
        if(nums[mid] == target)
            return mid; 
        else if (nums[mid] < target)
            left = mid + 1; / / note
        else if (nums[mid] > target)
            right = mid - 1; / / note
        }
return -1;
}
Copy the code

Reasons for using <= :

Left =mid+1 left=mid+1 left=mid+1 left=right =right +1 left=right +1

While (left < right) terminates with left == right, and may have changed one of the values in the last loop so that the value cannot be accessed

The above method terminates a return when it finds one, not necessarily the first one

Left = mid + 1, right = mid – 1 Right = mid or left = mid:

Since mid has already been searched, it should be removed from the search interval.

What are the drawbacks of this algorithm?

Unable to locate the first or last element. You might say, well, can’t you find a target and do a linear search to the left or right? Yes, but not good, because it’s hard to keep binary lookup logarithmic.

Binary search for the left edge

int[] searchRange(int[] nums, int target) {
    	int i = 0;
        int l = 0;int r = nums.length-1;
    	while(l<=r){
            int mid = l + r >>1;
            if(nums[mid]>target){
                r = mid - 1;
            }else if(nums[mid]<target){
                l = mid + 1;
            }else{
                i = mid;
                r = mid - 1; }}}Copy the code

It can also be written as:

int[] searchRange(int[] nums, int target) {
    	int i = 0;
        int l = 0;int r = nums.length-1;
        while(l<=r){
            int mid = l + r >>1;
            if(nums[mid]>=target){
                r = mid - 1;
                if(nums[mid]==target){ i = mid; }}else{
                l = mid + 1; }}}Copy the code

Instead of finding a number, this is a form where we can’t stop at finding a number, we have to keep narrowing down to the left until we find the leftmost element

If the value is equal to the value in the following paragraph, instead of directly returning, save the current value and reduce the right range to mid-1

else if(nums[mid]==target){
    i = mid;
    r = mid - 1;
}
Copy the code

Three, find the right edge of the binary search

int[] searchRange(int[] nums, int target) {
    	int i = 0;
        int l = 0;int r = nums.length-1;
    	while(l<=r){
            int mid = l + r >>1;
            if(nums[mid]>target){
                r = mid - 1;
            }else if(nums[mid]<target){
                l = mid + 1;
            }else{
                i = mid;
                l = mid + 1; }}}Copy the code

It can also be written as:

int[] searchRange(int[] nums, int target) {
    	int i = 0;
        int l = 0;int r = nums.length-1;
        while(l<=r){
            int mid = l + r >>1;
            if(nums[mid]<=target){
                l = mid + 1;
                if(nums[mid]==target){ i = mid; }}else{
                r = mid - 1; }}}Copy the code

Instead of finding a number, in this case we can’t stop at finding a number, we have to keep narrowing down to the right until we find the right most element

Return (mid+1); return (mid+1)

else if(nums[mid]==target){
    i = mid;
    l = mid + 1;
}
Copy the code

Small optimization tips

  • Use of MID calculation< < 1Instead of/ 2,
  • Prevent overflow: when L increases, L + R will be large, may overflow, can be usedl+((r-l)>>1)

Use it appropriately, using different binary lookups for different needs

Reference: leetcode-cn.com/problems/fi…

This article was automatically published by ArtiPub